【贪心】Coupons and Discounts

刺骨的言语ヽ痛彻心扉 2022-06-04 03:43 162阅读 0赞

Think:  
1知识点：贪心(局部最优解延展至全局最优解)  
2题意：输入一个序列(len <= 2e6)，代表n天内每天需要ai个披萨，现有两种获得披萨的方式，方式1(当前天直接得到两个披萨)，方式2(连续两天每天获得一个披萨)，询问能否在按照方式1和方式2的情况下满足n天的披萨要求(对于第i天不能少于ai亦不能多余ai)  
3思路：  
（１）：贪心算法：从第1天开始考虑，若第1天为奇数个披萨若想满足要求则必须通过方式2在第1天和第2天连续每天得到1个披萨，进而来到第2天，此时判断第2天在已经满足第1天的条件下剩余需要多少个披萨，若小于0即代表不能满足第1天的条件，若有奇数个披萨，进而考虑第3天能否满足通过方式2得到披萨(为什么不返回考虑第1天呢？因为若此时将第1天披萨数减1，第1天要么小于0不满足条件，要么又变成奇数个，需要再对第2天进行方式2试探，近似于无解循环，因为若第2天再减一就等效于直接对第2天进行方式1试探，还是会余下奇数个，因此应试探第3天)，不断进行局部最优解判断，最后通过全局最优解判断是否可以满足题意条件

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int rec[204014];
    
    int main(){
        int n, i;
        while(~scanf("%d", &n)){
            for(i = 0; i < n; i++){
                scanf("%d", &rec[i]);
            }
            bool flag = true;
            for(i = 0; i < n-1; i++){
                if(rec[i] < 0) {
                    flag = false;
                    break;
                }
                if(rec[i] & 1) {
                    rec[i+1] -= 1;
                }
            }
            if(rec[n-1] & 1) flag = false;
            if(flag) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/201483#problem/B