#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;    }*/