CF1054C.Candies Distribution
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are n children numbered from 1 to n in a kindergarten. Kindergarten teacher gave ai (1≤ai≤n) candies to the i-th child. Children were seated in a row in order from 1 to n from left to right and started eating candies.
While the i-th child was eating candies, he calculated two numbers li and ri — the number of children seating to the left of him that got more candies than he and the number of children seating to the right of him that got more candies than he, respectively.
Formally, li is the number of indices j (1≤j<i), such that ai<aj and ri is the number of indices j (i<j≤n), such that ai<aj.
Each child told to the kindergarten teacher the numbers li and ri that he calculated. Unfortunately, she forgot how many candies she has given to each child. So, she asks you for help: given the arrays l and r determine whether she could have given the candies to the children such that all children correctly calculated their values li and ri, or some of them have definitely made a mistake. If it was possible, find any way how she could have done it.
幼儿园里有 n 个孩子,编号从 1 到 n。幼儿园老师给第 i 个孩子分发了 ai(1≤ai≤n)颗糖果。孩子们按编号从左到右排成一排(即从 1 到 n),并开始吃糖果。
当第 i 个孩子在吃糖果时,他计算了两个数 li 和 ri:其中 li 表示坐在他左边且获得糖果数严格多于他的孩子人数;ri 表示坐在他右边且获得糖果数严格多于他的孩子人数。
形式化地,li 是满足 1≤j<i 且 ai<aj 的下标 j 的个数;ri 是满足 i<j≤n 且 ai<aj 的下标 j 的个数。
每个孩子都将自己算出的 li 和 ri 告诉了老师。不幸的是,老师忘记了当初给每个孩子分发了多少颗糖果。因此,她请你帮忙:给定数组 l 和 r,判断是否存在一种糖果分配方案 a1,a2,…,an,使得所有孩子均能正确计算出对应的 li 和 ri;若不存在,则说明至少有一名孩子肯定算错了。如果存在这样的分配方案,请给出任意一种可行方案。
输入格式
On the first line there is a single integer n (1≤n≤1000) — the number of children in the kindergarten.
On the next line there are n integers l1,l2,…,ln (0≤li≤n), separated by spaces.
On the next line, there are n integer numbers r1,r2,…,rn (0≤ri≤n), separated by spaces.
第一行包含一个整数 n(1≤n≤1000)—— 幼儿园中儿童的数量。
第二行包含 n 个整数 l1,l2,…,ln(0≤li≤n),以空格分隔。
第三行包含 n 个整数 r1,r2,…,rn(0≤ri≤n),以空格分隔。
输出格式
If there is no way to distribute the candies to the children so that all of them calculated their numbers correctly, print «NO» (without quotes).
Otherwise, print «YES» (without quotes) on the first line. On the next line, print n integers a1,a2,…,an, separated by spaces — the numbers of candies the children 1,2,…,n received, respectively. Note that some of these numbers can be equal, but all numbers should satisfy the condition 1≤ai≤n. The number of children seating to the left of the i-th child that got more candies than he should be equal to li and the number of children seating to the right of the i-th child that got more candies than he should be equal to ri. If there is more than one solution, find any of them.
如果不存在一种给孩子们分发糖果的方式,使得所有孩子都正确计算出了各自的数值,则输出 «NO»(不带引号)。
否则,在第一行输出 «YES»(不带引号)。在下一行输出 n 个整数 a1,a2,…,an,以空格分隔——分别表示第 1,2,…,n 个孩子获得的糖果数量。注意:这些数中可能有相等的,但所有数均需满足条件 1≤ai≤n。对于第 i 个孩子,坐在他左侧且获得糖果数多于他的孩子数量应恰好等于 li,坐在他右侧且获得糖果数多于他的孩子数量应恰好等于 ri。若存在多个解,输出任意一个即可。
输入输出样例
输入#1
5 0 0 1 1 2 2 0 1 0 0
输出#1
YES 1 3 1 2 1
输入#2
4 0 0 2 0 1 1 1 1
输出#2
NO
输入#3
3 0 0 0 0 0 0
输出#3
YES 1 1 1
说明/提示
In the first example, if the teacher distributed 1, 3, 1, 2, 1 candies to 1-st, 2-nd, 3-rd, 4-th, 5-th child, respectively, then all the values calculated by the children are correct. For example, the 5-th child was given 1 candy, to the left of him 2 children were given 1 candy, 1 child was given 2 candies and 1 child — 3 candies, so there are 2 children to the left of him that were given more candies than him.
In the second example it is impossible to distribute the candies, because the 4-th child made a mistake in calculating the value of r4, because there are no children to the right of him, so r4 should be equal to 0.
In the last example all children may have got the same number of candies, that's why all the numbers are 0. Note that each child should receive at least one candy.
在第一个例子中,如果老师分别向第 1、第 2、第 3、第 4、第 5 个孩子分发了 1、3、1、2、1 颗糖果,则所有孩子各自计算出的数值均正确。例如,第 5 个孩子得到了 1 颗糖果;他左侧有 2 个孩子各得到 1 颗糖果,1 个孩子得到 2 颗糖果,1 个孩子得到 3 颗糖果,因此他左侧共有 2 个孩子得到的糖果数多于他。
在第二个例子中,无法完成糖果分配,因为第 4 个孩子在计算 r4 的值时出现了错误:他右侧没有任何孩子,因此 r4 应等于 0。
在最后一个例子中,所有孩子可能都得到了相同数量的糖果,因此所有数值均为 0。注意:每个孩子至少应得到 1 颗糖果。
输入解题思路,AI测评打分。不知道怎么写?