爱丽丝是幼儿园的老师.她想给她班上的孩子们一些糖果.所有的孩子都坐在一条线上,每个孩子都根据他或她的平常表现得到评分.爱丽丝想给每个孩子至少给一个糖果.因为孩子们有点嫉妒.对于任何相邻的2个孩子,如果一个人的评分高于另一个,他/她必须得到比另一个更多的糖果,爱丽丝必须根据他们的评级主题给她的糖果.爱丽丝想要存钱,所以她想要总共提供少量糖果.
输入的第一行是一个整数N,即Alice类中的子节点数.以下每N行包含一个整数,表示每个孩子的评分.
在输出的唯一行上打印一个整数,描述Alice必须给出的最小糖果数量.
3
1
2
2
4
爱丽丝必须提供的糖果数量分别为1,2和1.
N 每个孩子的等级不大于10 ^ 5.
谁能帮帮我吗？
Sum*_*ndo 25
你可以两次通过.从拥有一个糖果的每个人开始.
第一个循环i从1到n-1(基于零),如果评级[i]>评级[i-1]则糖果[i] =糖果[i-1] +1
然后将i从n-2循环到0; 如果评级[i]>评级[i + 1]则糖果[i] = max(糖果[i],糖果[i + 1] +1)
这很容易显示这给你一个有效的糖果分布,因为第二个循环不会破坏第一个修复的任何东西,并且所有可能的评级差异必须由两个循环中的一个捕获.这将使用最少数量的糖果并不明显,但如果仔细检查每项任务,您可以证明条件证明每一步所需的糖果数量(由特定个体)的下限.
JPv*_*rwe 13
为了使这个算法的分析更有趣,我将进行以下输入:
9
2
3
4
4
4
2
1
3
4
首先,请注意,如果一个孩子坐在一个正在获得x糖果的孩子旁边,那个孩子的评分较低,那么第一个孩子应该至少得到x+1糖果.差异超过1只会浪费糖果.差异有时必须大于1,但我会在以后发生这种情况.
现在找到应该只获得一个糖果的孩子.我把收视率看作是一个山脉(评级越大,那个时候山脉越高),并找到那些应该得到一个糖果的孩子在山上找到山谷(两个邻居都有更高的评级或相同的评级)范围.给出的示例看起来像(箭头用箭头表示):
*** *
**** **
****** **
*********
^ ^ ^
出于这个过程的目的,我假设在该线的开始之前和结束之后有2个"无限"高度的峰值.(当我说无限时,我只是意味着比输入中任何可能的值都大,所以你可以只使用10^5+1"无穷大".实际上,我会使用一个大于那个问题设定者有错误输入数据的值.)
您可以使用以下代码轻松找到山谷:
ratings = ...
N = ...
valleys = []
def get_rating(i):
if i < 0 or i > N-1:
return INFINITY
return ratings[i]
for i from 0 to N-1:
if get_rating(i) <= get_rating(i-1) and get_rating(i) <= get_rating(i+1):
valleys.append(i)
该数组valleys包含山谷的索引.我们知道代表山谷的每个孩子应该得到一个糖果.为了说明,假设山谷在索引4处.现在我们知道指数3和5的孩子应该至少获得2个糖果.如果指数2的孩子的评分高于指数3的孩子那么孩子应该得到至少3个糖果.等等为2和向下.同样适用于6岁及以上.
注意我说"至少",这是因为峰值(孩子的等级高于他们的邻居的两个,注意不同于山谷我在这个定义中不包括相等).峰值可以有两个最小约束,我们只选择两个中的较大者.
现在我们可以通过以下代码找到每个孩子应该得到的糖果数量:
candies = [0] * N # An array of N 0s
for valley_idx in valleys:
candies[valley_idx] = 1
cur_idx = valley_idx-1
cur_candies = 2
while cur_idx >= 0 and ratings[cur_idx] > ratings[cur_idx+1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx -= 1
cur_candies += 1
cur_idx = valley_idx+1
cur_candies = 2
while cur_idx < N and ratings[cur_idx] > ratings[cur_idx-1]:
candies[cur_idx] = max(candies[cur_idx], cur_candies)
cur_idx += 1
cur_candies += 1
然后教师需要购买的糖果数量是candies数组中值的总和.
这样做的答案结果是18我们的样本输入或图表形式:
* * *
** ** **
*********
在上面的解决方案中,我假设具有相同评级的相邻孩子不会对糖果的数量施加任何限制.如果它是两个孩子都需要获得相同数量的糖果的情况,我们可以很容易地改变算法以考虑到这一点.
基本的想法是我们做一种运行长度编码,因为我们可以注意到连续有一个或多个孩子具有相同的评级,它不会改变他们的邻居应该得到的糖果数量.我们需要连续跟踪孩子的数量,因为连续5个孩子得到5个糖果意味着我们必须发出25个糖果而不仅仅是5个.我们用multipliers阵列做这个.使用以下代码,我们找到新的ratings数组和multipliers数组:
new_ratings = [ratings[0]]
multipliers = [1]
for i from 1 to N-1:
if ratings[i] == new_ratings[len(new_ratings)-1]:
multipliers[len(new_ratings)-1] += 1
else:
new_ratings.append(ratings[i])
multipliers.append(1)
现在我们只需在new_ratings数组上运行原始算法并获得一个candies数组.然后,为了获得我们可以运行的实际糖果量:
answer = 0
for i from 0 to len(new_ratings)-1:
answer += multipliers[i] * candies[i]
这样做的答案结果是20我们的样本输入或图表形式:
*** *
***** **
*********
我用简单的DP方法来解决这个问题.如果你的评级大于前一个,则增加DP表中的第i个值,否则可能有两个条件.一个条件是先前索引的DP值为1然后以相反的顺序遍历,直到您获得小于其下一个值的值并继续更新DP.另一个条件是先前索引的DP值大于1,在那种情况下,DP中的当前索引被赋值为1.
for(int i=1; i <= n; i++){
scanf("%d", ra+i);
if( ra[i] > ra[i-1] )
dp[i] = dp[i-1] + 1;
else if( dp[i-1] == 1 ){
dp[i] = 1;
for( int j=i-1; j>0; j-- )
if( ra[j] > ra[j+1] )
dp[j] = max ( dp[j+1] + 1, dp[j] );
else
break;
}
else
dp[i] = 1;
}
long long sum = 0;
for(int i = 1;i <= n; i++)sum+= dp[i];
printf("%lld\n",sum);
实际上这个问题可以通过在数组上传递两次来解决.并且解决方案将是O(N)时间.我通过使用geeksforgeeks Trapping Rain Water(http://www.geeksforgeeks.org/trapping-rain-water/)问题解决了这个问题.同样的原则可以应用于这个问题.
首先,我们有两个规则. - 每个学生至少获得1个糖果. - 每个学生的评分都高于他/她的邻居(下一个或前一个学生),他将获得至少一个糖果.
正如我所说,我们需要两个传递数组.第一个是从左到右; - 首先,我们将为第一个分配一个糖果. - 然后通过检查当前的一个是否具有更高的评级然后给他一个比前一个学生多一个来循环数组,否则给他一个糖果.
第二遍将是从右到左. - 这次我们开始为最后一个分配一个糖果. - 然后从右到左遍历数组,并在第一个循环中执行类似的操作.
在这两个循环之后,我们将通过获取数组的最大值来左右循环,并将此值添加到总糖果中.
Test cases :
input : { 1, 2, 2 }
output : { 1, 2, 1 } => 4
input : { 9, 2, 3, 4, 4, 4, 2, 1, 3, 4 }
output : { 2, 1, 2, 3, 1, 3, 2, 1, 2, 3 } => 20
您可以在下面找到针对此问题的Java解决方案.
public int calculate(int[] arr) {
int m = arr.length;
int[] left = new int[m];
int[] right = new int[m];
int candies = 0;
left[0] = 1;
for (int i = 1; i < m; i++)
left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
right[m - 1] = 1;
for (int i = m - 2; i >= 0; i--)
right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
for (int i = 0; i < m; i++)
candies += Math.max(left[i], right[i]);
return candies;
}
假设我们有
1、5、2、10、10、3、8、9、1、1、2作为11名学生S1至S11的评分
假设我们制作了一个图表评分与学生的图表，其中评分绘制在y轴上，然后
局部最小值将总是得到一个糖果，因此学生S1，S3，S6，S9和S10将是局部最小值并且将得到一个糖果。我们可以说有一个最小解决方案（So）偏离了我们说的话，然后我们可以再创建一个解决方案（So1），其中所有学生都得到相同的糖果，而局部最小值则偏离一个糖果，那么So1将是最小值，因此，如果局部最小值获得的糖果大于1，就没有最小解。
一旦获得局部最小值的值，就可以横向横穿最小值的左侧和右侧以计算其他学生的糖果。
对于局部最大值，其相邻节点+1的值将更大。工作代码如下，时间复杂度为O（n），空间复杂度为O（n）
public static int candy(ArrayList<Integer> a) {
int size = a.size();
int[] cand = new int[size];
// give all children candies equal to 1
// local minimas will get 1
for(int i = 0; i < size; i++)
{
cand[i] = 1;
}
// increase count on the right of local minimas
for(int i = 1; i < size; i++)
{
if(a.get(i) > a.get(i-1))
{
cand[i] = cand[i-1]+1;
}
}
// increase count on the left of local minimas
// local maximas should be max of left and right
for(int i = size-2; i >= 0; i--)
{
if(a.get(i) > a.get(i+1))
{
cand[i] = Math.max(cand[i], cand[i+1]+1);
}
}
// get the sum
int count = 0;
for(int i = 0; i < size; i++)
{
count = count + cand[i];
}
return count;
}
您可以在HackerEarth问题中使用测试用例进行测试：https ://www.hackerrank.com/challenges/candies
Leetcode：https ://leetcode.com/problems/candy/
您可以在http://stackandqueue.com/?p=108上找到有关其工作原理的详细说明。
| 归档时间： |
|
| 查看次数： |
24377 次 |
| 最近记录： |