首页 > 代码库 > CSDN 分糖果算法的思路和求助
CSDN 分糖果算法的思路和求助
昨天晚上 在csdn上做了一道分糖果的题目，我自个测的是没有问题，但是提交答案后，老失败，提示
你的程序正常运行并输出了结果，但是答案错误
你的程序输出结果与测试数据中的输出结果不符
我先把自个思路说一下，再把我的代码贴出来，你们帮忙看看，哪里出了问题，或者有更好的思路分享下。
题目是这样的：地址：http://student.csdn.net/mcs/programming_challenges 第二道题目
有n个小朋友站成一排（编号从0到n-1)，每个小朋友有一个rating值，存放在ratings数组中。老师需要给他们分配糖果，每个小朋友至少需要一颗糖果，对于任意相邻的两个小朋友i和i+1，rating值大的必须比rating值小的分配的糖果多（rating相同的没必要分配一样多的糖果）。请计算最少需要多少颗糖果，才能完成上述分配。输入格式：多组数据，每组数据第一行是一个正整数n。接下来n行,每行有1个正整数，表示每个小朋友的rating值。所有整数都不超过100000。输出格式：每组数据一行，包括一个正整数，表示做少需要的糖果数。
我的思路是 从0开始遍历小朋友，每一次求出当前小朋友可以拿到的最少糖果数，每一次比对前后位置；
前面的位置比对一次就可以了，若大于前面小朋友的rating值，则当前应该得到的糖果数为上一位小朋友得到的糖果数+1，若小于等于前面小朋友的rating值，则自动将应得糖果数变为1；
设置往后比对应得糖果数为1的临时变量，然后开始往后面比对，如果后面小朋友的rating值，小于当前小朋友的rating值，则当前小朋友应得糖果数的临时变量+1，继续比对后面小朋友，如果是递减，则不断+1，直到递减结束;
比对该临时变量和往前比对应得糖果数，取二者的最大值,即为当前小朋友应得最少糖果数。
这样求出每次小朋友应得最少糖果数，依次相加即可得到最少糖果数。
具体代码如下：
1 static void Main(string[] args) 2 { 3 Console.WriteLine("输入n跳出循环，或者其他字符开始游戏"); 4 while (Console.ReadLine() != "n") 5 { 6 GetMin(); 7 Console.WriteLine("输入n跳出循环，或者其他字符继续游戏"); 8 } 9 10 }11 static void GetMin()12 {13 // Console.WriteLine("请输入整数");14 15 string input = Console.ReadLine();16 int inputNum;17 while (!int.TryParse(input, out inputNum))18 {19 // Console.WriteLine("请输入整数");20 input = Console.ReadLine();21 }22 if (inputNum == 0)23 {24 Console.WriteLine("0");25 return;26 }27 28 29 int[] arys = new int[inputNum];30 //Random rm=new Random();31 //for (int i = 0; i < inputNum; i++)32 //{33 // arys[i] = rm.Next(1, 15);34 // Console.Write(arys[i]+" ");35 //}36 //Console.WriteLine();37 38 int tmp;39 for (int i = 0; i < inputNum; i++)40 {41 input = Console.ReadLine();42 while (!int.TryParse(input, out tmp) || tmp > 100000 || tmp <= 0)43 {44 Console.WriteLine("请输入不超过100000的正整数");45 input = Console.ReadLine();46 }47 arys[i] = tmp;48 }49 50 int sum = 0;51 int num = 1;52 int j;53 //遍历每个小朋友54 for (int i = 0; i < arys.Length; i++)55 {56 j = i;57 //往前比对 求出应得最少糖果数58 if (j >= 1 && arys[j] > arys[j - 1])59 {60 num++;61 }62 else63 {64 num = 1;65 }66 //开始往后比对，求出往后比对应得最少糖果数67 int next = 1;68 while (j < arys.Length - 1 && arys[j] > arys[j + 1])69 {70 j++;71 next++;72 }73 //比对 往前比对和往后比对的结果 取二者中最大值 作为应得最少糖果数74 num = num > next ? num : next;75 //Console.WriteLine("num:" + num);76 sum += num;77 }78 Console.WriteLine("最少应得糖果数" + sum);79 }
CSDN 分糖果算法的思路和求助
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。