怎么用C++解決分糖果問(wèn)題

本篇內(nèi)容主要講解“怎么用C++解決分糖果問(wèn)題”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么用C++解決分糖果問(wèn)題”吧!

分糖果問(wèn)題

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?

這道題看起來(lái)很難，其實(shí)解法并沒(méi)有那么復(fù)雜，當(dāng)然我也是看了別人的解法才做出來(lái)的，先來(lái)看看兩遍遍歷的解法，首先初始化每個(gè)人一個(gè)糖果，然后這個(gè)算法需要遍歷兩遍，第一遍從左向右遍歷，如果右邊的小盆友的等級(jí)高，等加一個(gè)糖果，這樣保證了一個(gè)方向上高等級(jí)的糖果多。然后再?gòu)挠蚁蜃蟊闅v一遍，如果相鄰兩個(gè)左邊的等級(jí)高，而左邊的糖果又少的話，則左邊糖果數(shù)為右邊糖果數(shù)加一。最后再把所有小盆友的糖果數(shù)都加起來(lái)返回即可。代碼如下：

解法一：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0, n = ratings.size();
        vector<int> nums(n, 1);
        for (int i = 0; i < n - 1; ++i) {
            if (ratings[i + 1] > ratings[i]) nums[i + 1] = nums[i] + 1;
        }
        for (int i = n - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i]) nums[i - 1] = max(nums[i - 1], nums[i] + 1);
        }
        for (int num : nums) res += num;
        return res;
    }
};

下面來(lái)看一次遍歷的方法，相比于遍歷兩次的思路簡(jiǎn)單明了，這種只遍歷一次的解法就稍有些復(fù)雜了。首先我們給第一個(gè)同學(xué)一個(gè)糖果，那么對(duì)于接下來(lái)的一個(gè)同學(xué)就有三種情況：

1. 接下來(lái)的同學(xué)的rating等于前一個(gè)同學(xué)，那么給接下來(lái)的同學(xué)一個(gè)糖果就行。

2. 接下來(lái)的同學(xué)的rating大于前一個(gè)同學(xué)，那么給接下來(lái)的同學(xué)的糖果數(shù)要比前一個(gè)同學(xué)糖果數(shù)加1。

3.接下來(lái)的同學(xué)的rating小于前一個(gè)同學(xué)，那么我們此時(shí)不知道應(yīng)該給這個(gè)同學(xué)多少個(gè)糖果，需要看后面的情況。

對(duì)于第三種情況，我們不確定要給幾個(gè)，因?yàn)橐侵唤o1個(gè)的話，那么有可能接下來(lái)還有rating更小的同學(xué)，總不能一個(gè)都不給吧。也不能直接給前一個(gè)同學(xué)的糖果數(shù)減1，有可能給多了，因?yàn)槿绻竺嬖贈(zèng)]人了的話，其實(shí)只要給一個(gè)就行了。還有就是，如果后面好幾個(gè)rating越來(lái)越小的同學(xué)，那么前一個(gè)同學(xué)的糖果數(shù)可能還得追加，以保證最后面的同學(xué)至少能有1個(gè)糖果。來(lái)一個(gè)例子吧，四個(gè)同學(xué)，他們的rating如下：

1 3 2 1

先給第一個(gè)rating為1的同學(xué)一個(gè)糖果，然后從第二個(gè)同學(xué)開始遍歷，第二個(gè)同學(xué)rating為3，比1大，所以多給一個(gè)糖果，第二個(gè)同學(xué)得到兩個(gè)糖果。下面第三個(gè)同學(xué)，他的rating為2，比前一個(gè)同學(xué)的rating小，如果我們此時(shí)給1個(gè)糖果的話，那么rating更小的第四個(gè)同學(xué)就得不到糖果了，所以我們要給第四個(gè)同學(xué)1個(gè)糖果，而給第三個(gè)同學(xué)2個(gè)糖果，此時(shí)要給第二個(gè)同學(xué)追加1個(gè)糖果，使其能夠比第三個(gè)同學(xué)的糖果數(shù)多至少一個(gè)。那么我們就需要統(tǒng)計(jì)出多有個(gè)連著的同學(xué)的rating變小，用變量cnt來(lái)記錄，找出了最后一個(gè)減小的同學(xué)，那么就可以往前推，每往前一個(gè)加一個(gè)糖果，這就是個(gè)等差數(shù)列，我們可以直接利用求和公式算出這些rating減小的同學(xué)的糖果之和。然后我們還要看第一個(gè)開始減小的同學(xué)的前一個(gè)同學(xué)需不需要追加糖果，只要比較cnt和pre的大小，pre是之前同學(xué)得到的最大糖果數(shù)，二者做差加1就是需要追加的糖果數(shù)，加到結(jié)果res中即可，參見代碼如下：

解法二：

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.empty()) return 0;
        int res = 1, pre = 1, cnt = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] >= ratings[i - 1]) {
                if (cnt > 0) {
                    res += cnt * (cnt + 1) / 2;
                    if (cnt >= pre) res += cnt - pre + 1;
                    cnt = 0;
                    pre = 1;
                }
                pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
                res += pre;
            } else {
                ++cnt;
            }
        }     
        if (cnt > 0) {
            res += cnt * (cnt + 1) / 2;
            if (cnt >= pre) res += cnt - pre + 1;
        }
        return res;
    }
};

到此，相信大家對(duì)“怎么用C++解決分糖果問(wèn)題”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！