题意
给出一个序列，每次操作都能使得相邻的三个数字减1，并且有一次机会，能直接让两个相邻的数字变为0，现在求最多要多少次操作才能让数字都<=0
解析
- List item
- 假设不动用机会，我们如何把所有数字变为<=0 ，对于最左边的数字假设是a[1]，那么我们一定要花费a[1]次操作，将a[1]处理完，对于数字a[2]已经是边界，因此我们必须要花费a[2]-a[1]的操作，但是我们不知道a[2]-a[1]是否大于0，那么就要max(0,a[2]-a[1])，因此我们可以按这样最优的贪心下来算出最终结果。
- 由于只需要<=0即可，所以我们使用机会让两个数字为0不确定放在哪，那么我们是否可以遍历机会使用的位置，并且通过O(1)的时间得到结果呢?
- 答案是，前缀和。
- 首先我们不用机会，朴素的算下来，得到每个从前到后，从后到前的前缀，如果我们对a[i],a[i+1]使用机会，那么左边和右边就互不影响，我们用刚刚算的前缀即可O(1)时间得到结果。
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; ll a[N],b[N],L[N],R[N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]; } for(int i=1;i<=n;i++){ L[i]=L[i-1]+a[i]; a[i+1]=max(0ll,a[i+1]-a[i]); a[i+2]=max(0ll,a[i+2]-a[i]); } for(int i=n;i>=1;i--){ R[i]=R[i+1]+b[i]; if(i>=2){ b[i-1]=max(0ll,b[i-1]-b[i]); b[i-2]=max(0ll,b[i-2]-b[i]); } } ll res=1e18; for(int i=1;i<=n;i++){ res=min(res,L[i-1]+R[i+2]); } printf("%lld",res); } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/123190.html