[leetcode/lintcode 題解] 阿裡巴巴面試題：澆花

描述

你和你的朋友都是園丁，你們要照顧好你們的植物。這些植物是連續種植的，而且每種植物都需要一定量的水。你們要用水罐給它們澆水。為了避免錯誤，比如澆水太多，或者根本不給植物澆水，你們決定：

按植物出現的順序澆水：你要從左到右澆水，你的朋友要從右到左澆水；

如果你有足夠的水來澆灌每一棵植物，否則請重新裝滿你的水壺；

一次澆灌每株植物，即在給一株植物澆灌的過程中，不需要休息一下就可以重新灌滿澆灌罐。這意味需要在澆灌植物之前或之後重新灌滿澆水罐，即使澆水罐不是完全空的。

你從澆灌第一株植物開始，你的朋友從澆灌最後一株植物開始，你和你的朋友同時澆灌植物（當你澆灌第一株植物時，你的朋友澆灌最後一株；當你澆灌第二株植物時，你的朋友澆灌倒數第二株植物；

等等）這意味着你們将在一排植物中間相遇。如果那裡有一棵沒有澆水的植物，而且你和你的朋友一起有足夠的水來澆水，你可以不用再裝滿你的水罐來澆水；否則，你們中隻有一個人需要再重灌。

一開始你們的澆水罐都是空的，你和你的朋友需要給你的澆水罐重灌多少次水才能澆灌整排的植物？

Write a function:：

class Solution{public int solution(int[] plants, int capacity1, int capacity2);}

給定一個包含n個整數（表示每株植物所需的水量）的數組和變量capacity1和capacity2（表示你和你朋友的澆水罐的容量），則傳回你和你朋友需要重新裝滿澆水罐來澆灌所有植物的次數。

• N 的範圍[1..1,000];
• plants數組中每個元素範圍[1..1,000,000];
• capacity1 和 capacty2 範圍[1..1,000,000,000];
• 兩個澆水罐都足夠大，可以完全澆灌任何一株植物。

線上評測位址：

領扣題庫官網

樣例1
Input：[2,4,5,1,2],5,7
Output：3
Explanation：First you refill and water plants[0] and simultaneously your friend refills and waters plants[4].Then you refill and water plants[1] and simultaneously your friend waters plants[3].Finally you water plants[2] togerther (as together you have exactly 5 units of water).           

樣例2
Input：[43,48,29],49,34
Output：3
Explanation：First you water the plants [0], your friends water the plants [2], and finally you water the plants [1].           

考點

模拟

題解

按照題意模拟，最後相遇時特判兩人能否一起澆灌最後一株植物即可。

class Solution {
public:
    int waterPlants(vector<int> &plants, int capacity1, int capacity2) {
        int can1 = 0;
        int can2 = 0;
        int lo = 0;
        int hi = plants.size() - 1;
        int numRefils = 0;
        while (lo < hi) {
            if (can1 < plants[lo]) {
                can1 = capacity1;
                ++numRefils;
            }
            if (can2 < plants[hi]) {
                can2 = capacity2;
                ++numRefils;
            }
            can1 -= plants[lo++];
            can2 -= plants[hi--];
        }
        if (lo == hi && (plants[lo] > can1 + can2)) {
            return ++numRefils;
        } 
        else {
            return numRefils;
        }
        
    }
};           

更多題解參考：九章官網solution

https://www.jiuzhang.com/solution/watering-flowers/?utm_source=sc-tianchi-sz-0226