题解 P3078 【[USACO13MAR]Poker Hands S】

k3v1n070828 · 2020-04-02 13:51:56 · 题解

一道非常简单的贪心题

说下思路：

可以发现填平一个坑的同时，旁边的坑也会连带着被填一些。

∴旁边没填满的那个大坑会连带减少减少a[i]-a[i-1]的深度。

从第一个坑开始用循环：下一个坑是否能被连带着填满，如果不是的话，用ans记录每次的a[i]-a[i-1]。最后输出第一个坑的深度（无法被连带着填满）+ans(后面的坑需要的天数)。

用贪心做代码十分的简洁，唯一需要注意的一点是需要开long long。

话不多说，上代码：

#include<cstdio>
using namespace std;
long long n,a[100005];//十年OI一场空，不开long long见祖宗
long long ans=0;
int main(){
    scanf("%lld",&n);//输入
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);//输入
    for(int i=2;i<=n;i++)
        if(a[i]>a[i-1]) ans+=a[i]-a[i-1];//如果旁边坑没被填满，那就增加a[i]-a[i-1]天
    printf("%lld\n",a[1]+ans);//输出
    return 0;
}

蒟蒻的第一篇黄题题解，给蒟蒻点个赞呗

最后，望管理员通过，谢谢！