它就是一个贪心。
题目里给的样例是4,3,2,5,3,5;
可以选择一个区间进行“填坑” *** 作;
所以我们的贪心策略是:
若a[i]>a[i-1],计数器sum+=a[i]-a[i-1];
那么为什么这样贪心是对的呢?
贪心证明
假设现在有一个坑,但旁边又有一个坑。
你肯定会选择把两个同时减1;
那么小的坑肯定会被大的坑“带着”填掉。
大的坑也会减少a[i]-a[i-1]的深度,可以说是“免费的”;
所以这样贪心是对的;
注:由于第一个坑左边没有坑,我们可以认为有一个为0的即(0,4,3,2,5,3,5)
#includeusing namespace std; int n,a[100005]; long long ans=0; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=2;i<=n;i++) if(a[i]>a[i-1]) ans+=a[i]-a[i-1]; cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)