leecode 解题总结：135. Candy

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:There are N children standing in a line. Each child is assigned a rating value.You are giving candies to these children subjected to the following requirements:Each child must have at least one candy.Children with a higher rating get more candies than their neighbors.What is the minimum candies you must give?分析: rating value排名。N个孩子站成一排，每个人被分配了一个排名值。你需要给孩子分配糖果：每个孩子至少有一个糖果，较高排名的孩子需要比他的邻居都要多。这里第二点有歧义，较高排名的比左边较低排名的多，比右边较低排名的多。举例：r:1 5 2 4 3设n个人每个人分配的糖果为x[i],i从1到N根据当前题目:x[1] < x[2]x[2] > x[3]x[3] < x[4]x[4] > x[5]难点在于不知道从哪个地方选取赋予最少的糖果，假设我们选取排名最小的第一个孩子，发一个糖果那么x[1]=1,根据关系式:x[2] >= 2,    x[3] <= 1,	x[4] >= 2	x[5] <= 1	综上，最少糖果为: 1 + 2 + 1 + 2 + 1 = 7假设是:r:1 2 3 4 5则糖果至少为:1 + 2 + 3 + 4 + 5 = 15如果是:r:5 4 3 2 1糖果也是:5 + 4 + 3 + 2 + 1 = 15如果是:r:4 2 1 3 5,那么糖果是: 3 + 2 + 1 + 2 + 3 = 11r:4 3 1 5 3糖果是: 3 + 2 + 1 + 2 + 1 = 9发现：将一个高排名的左右安排比他排名低的，比一直按排名升序或降序排列好如果仅仅是给定排名，我们可以得到一个关系式，利用关系式来推出当前第i个孩子，至少要分配多少糖果。顺序可以从前向后递推。如果是: 1 2 6 5 4 3,那么就需要: 1 + 2 + 4 + 3 + 2 + 1 = 13也就是可以确定发送糖果最多的个数= 寻找到的排名单调增区间或者单调减区间的最大长度以1 2 6 5 4 3为例找到最大单调递增区间是{1,2,6}，最大单调减区间是{6,5,4,3}，所以发给的糖果个数等于4，将该最长的单调增区间或减区间左右分成两半，对左边继续上述操作，对右边继续寻找上述操作累加结果。这个应该是分治算法。如果出现多个相同长度的单调区间，随便选择一个，即可。dp[i][j]表示从A[i...j]花费的最少糖果数分析时间复杂度：每次先要找到当前部分中长度最长的单调区间，耗时O(n)，然后将数组分成左边和右边，对左边和右边重复上述过程总的时间复杂度为O(n^2)竟然有排名相同的，排名相同的可以给相同的糖果。这个不影响给出的单人最高糖果数量我需要修改的地方：比如给定的是1 1 2 2 3 3:那么长度为6，但是不重复元素数量为3，最高糖果数为3，然后还得遍历一把输入:61 2 6 5 4 351 2 3 4 551 5 2 4 31212 9 2 7 8 6 5 3 4 1 11 101110 9 2 7 8 6 5 10 3 1 111122 231 2 2输出:131572320124报错:Input:[1,2,2]Output:5Expected:4为什么?别人的解法:http://www.cnblogs.com/AndyJee/p/4483043.html关键：1可以从题目角度来看：从前到后，如果后面人排名比前面人高，后面人给的糖果数=前面一个人给的糖果数+1但是后面<=前面的情况无法判断，我们暂时不处理。然后从后向前，每个元素与其后面的元素比较，如果ratings[i] > ratings[i+1]，且令candy[i] = max(candy[i] , ratings[i+1]+1)，因为至少要比后面的人多1题目中没有说明如果两个人排名相同是否需要给相同数量的糖果，所以1,2,2.只需要1 + 2 + 1共4颗。2 典型的双向贪心算法*/class Solution {public:    int candy(vector<int>& ratings) 	{		if(ratings.empty())		{			return 0;		}		if(ratings.size() <= 1)		{			return 1;		}		int size = ratings.size();		vector<int> candyNum(size , 1);//初始化每个人至少一个糖果		for(int i = 1 ; i < size ; i++)		{			//如果从前向后遍历，元素>前面元素，则元素的糖果数=前面元素的糖果数+1			if(ratings.at(i) > ratings.at(i-1))			{				candyNum.at(i) = candyNum.at(i-1) + 1;			}		}		//从后向前遍历， 当前元素>后面元素，则当前元素糖果数=max(当前元素糖果数，后面元素糖果数+1)，		//取较大值，才能满足比两边相邻较小排名分得的糖果数更多一点		int result = candyNum.at(size - 1);		//逆序遍历,i--		for(int i = size - 2; i >= 0; i--)		{			if(ratings.at(i) > ratings.at(i+1))			{				candyNum.at(i) = max(candyNum.at(i) , candyNum.at(i+1) + 1);			}			result += candyNum.at(i);		}		return result;	}};void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 num = solution.candy(nums);		 cout << num << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*public:	//计算某个单调区间的总糖果数，以及最高糖果数	int calculate(vector<int>& ratings , int beg , int end, bool isIncreasing)	{		if(ratings.empty() || beg < 0 || end >= ratings.size() || beg > end)		{			return 0;		}		//如果只有一个元素，直接返回1		if(beg == end)		{			return 1;		}				int result = 0;		int curNum;		//如果是递增的		if(isIncreasing)		{			result = 1;			curNum = 1;			for(int i = beg + 1 ; i <= end ; i++)			{				//后面不等于前面				if(ratings.at(i) != ratings.at(i-1))				{					curNum++;				}				//相同元素，curNum不变，				result += curNum;			}		}		else		{			result = 1;			curNum = 1;			for(int i = end - 1 ; i >= beg ; i--)			{				//后面不等于前面				if(ratings.at(i) != ratings.at(i+1))				{					curNum++;				}				//相同元素，curNum不变，				result += curNum;			}		}		return result;	}	int getCandy(vector<int>& ratings , int beg , int end)	{		if(ratings.empty() || beg < 0 || end >= ratings.size() || beg > end)		{			return 0;		}		//如果只有一个元素，直接返回1		if(beg == end)		{			return 1;		}		//如果剩余部分从beg到end为单调增区间或减区间，直接返回结果是从1到end-beg的累加和		int decrementBeg = beg;		int decrementEnd = beg;		int incrementBeg = beg;		int incrementEnd = beg;		int realDecrementBeg = beg;		int realDecrementEnd = beg;		int realIncrementBeg = beg;		int realIncrementEnd = beg;		int maxIncrementLen = 1;		int maxDecrementLen = 1;		//先计算从beg到end中最长单调增区间和单调减区间，需要记录各自的下标		for(int i = beg + 1 ; i <= end ; i++)		{			//寻找最长单调增区间，相同的元素也包含进来			if(ratings.at(i) >= ratings.at(i-1))			{				incrementEnd = i;			}			//说明后面比前面小，是单调减区间，此时应该计算单调增区间的长度,如果遇到相同的元素，不算			else			{				if(incrementEnd - incrementBeg + 1 > maxIncrementLen)				{					maxIncrementLen = incrementEnd - incrementBeg + 1 ;					realIncrementBeg = incrementBeg;					realIncrementEnd = incrementEnd;				}				//需要重新设定单调增区间的起始点和结束点为当前				incrementEnd = incrementBeg = i;			}			//寻找最长单调增区间			if(ratings.at(i) <= ratings.at(i-1))			{				//累加单调减区间的结束值				decrementEnd = i;			}			//说明后面比前面小，是单调减区间，此时应该计算单调增区间的长度			else			{				//计算单调减区间的长度				if( decrementEnd - decrementBeg + 1 > maxDecrementLen)				{					maxDecrementLen = decrementEnd - decrementBeg + 1;					realDecrementBeg = decrementBeg;					realDecrementEnd = decrementEnd;				}				//更新单调减区间的起始值为当前下标				decrementBeg = decrementEnd = i;			}		}		//可能存在一种情况，一直到最后一个元素都一直降序或升序，导致遗漏一次，需要计算		if(incrementEnd - incrementBeg + 1 > maxIncrementLen)		{			maxIncrementLen = incrementEnd - incrementBeg + 1 ;			realIncrementBeg = incrementBeg;			realIncrementEnd = incrementEnd;		}		if( decrementEnd - decrementBeg + 1 > maxDecrementLen)		{			maxDecrementLen = decrementEnd - decrementBeg + 1;			realDecrementBeg = decrementBeg;			realDecrementEnd = decrementEnd;		}		//比较单调增区间和单调减区间谁的长度长，就选择谁的长度作为最高糖果数，并将区间划分		int realBeg;		int realEnd;		int maxLen = max(maxIncrementLen , maxDecrementLen);		//判断从beg到end是否一直是升序或降序，如果是，就直接计算出结果并返回		if(maxLen == end - beg + 1)		{			int sum = 0;			if(maxLen == maxIncrementLen)			{				sum = calculate(ratings , beg , end , true);			}			else			{				sum = calculate(ratings , beg , end , false);			}			return sum;		}		if( maxIncrementLen > maxDecrementLen)		{			realBeg = realIncrementBeg;			realEnd = realIncrementEnd;		}		else		{			realBeg = realDecrementBeg;			realEnd = realDecrementEnd;		}		//将区间划分成左右不分，		int leftResult = getCandy(ratings , beg , realBeg - 1);		int rightResult = getCandy(ratings , realEnd + 1 , end);		int result = 0;		if(maxLen == maxIncrementLen)		{			result = calculate(ratings , realBeg, realEnd , true);		}		else		{			result = calculate(ratings , realBeg, realEnd , false);		}		result += leftResult + rightResult;		return result;	}    int candy(vector<int>& ratings) {		if(ratings.empty())		{			return 0;		}		int result = getCandy(ratings , 0 , ratings.size() - 1);		return result;    }*/