[LeetCode]Candy——キャンディの問題

2643 ワード

一、問題の説明:
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? https://leetcode.com/problems/candy/
二、問題を解く構想:
これは局所的な貪欲な問題であり,配列全体に対して複数の厳密に単調に増加し,厳格に単調に減少する組合せ区間に分割し,各区間内部で最小のキャンディ戦略を用いた.区間の先頭要素と前の区間の末尾要素の大きさの問題を考慮する必要があることに注意してください.この要素が前の区間の末尾要素より小さい場合は、1を付与すればいいです.そうしないと、2を付与する必要があります.
三、コード:beats 90%submissions in c+=.=

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI (acos(-1.0))
#define EPS (1e-8)
#define INF (1<<30)
using namespace std;
class Solution {
public:
    int candy(vector& ratings) {
        if (ratings.size() <= 1) return ratings.size();
        int left=0, right=0, pos=0, n=ratings.size(), sum=0;
        while(left < n) {
        	int i, lval = 1, rval;
        	if(left!=0 && ratings[left]>ratings[left-1]) lval++;
        	for(i = left+1; iratings[i-1]; i++) {// gradient increase
        		sum += lval;
        		if (ratings[i] > ratings[i-1]) lval++;
        	}
        	pos = --i; // find local max
        	for(right = i+1; right pos; i--) {
        		sum += rval;
        		if (ratings[i] < ratings[i-1]) {
        			rval++;
        		}
        	}
        	sum += max(max(lval, rval), 1);
        	// cout << "sum: " << sum << ", lval: " << lval << ", rval: " << rval << endl;
        	left = right+1;
        }
        return sum;
    }
};
int main(int argc, char const *argv[]) {
	int cnt, x;
	Solution solu;
	vector v;
	cin >> cnt;
	while(cnt--) {
		cin >> x;
		v.push_back(x);
	}
	cout << solu.candy(v) << endl;
	return 0;
}

[アルゴリズム]Bobmer

Leetcode組合せ総和シリーズの詳細