博客

问题描述：有不同分数的小孩排队，怎么分糖果使得糖果数最小，且分数高的小孩分到尽可能多的糖果。

分析：每个小孩至少可分到一个糖果，且分数不固定，所以分数高的小孩要尽可能的只比旁边的两个人分的糖果多，而分数低的要尽可能的少。

解题思路：分别从前后进行扫描，让每个小孩都能分到糖果，保证分数高的尽可能多于两边的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <vector>
using namespace std;

#define MAX_QUEUE 10240 + 10

int main(int argc, char** argv) {
	int i_queue[MAX_QUEUE] = { 0 };

	int i = 0;
	cin >> i_queue[i++];
	while (getchar() == ',') {
		cin >> i_queue[i++];
	}

	vector<int> suger(i, 1);
	for (int i_idx = 1; i_idx < i; i_idx++) {
		if (i_queue[i_idx] > i_queue[i_idx - 1])
			suger[i_idx] = suger[i_idx - 1] + 1;
	}

	for (int i_idx = i - 2; i_idx >= 0; i_idx--) {
		if (i_queue[i_idx] > i_queue[i_idx + 1] && suger[i_idx] <= suger[i_idx + 1])
			suger[i_idx] = suger[i_idx + 1] + 1;
	}

	int min = 0;
	for (int j = 0; j < i; j++)
		min += suger[j];

	cout << min << endl;

	system("pause");
	return 0;
}

例如：输入5,4,1,1 输出7