【贪心+最小子段和】EDU151 D

电玩女神 2024-03-17 16:30 31阅读 0赞

[Problem - D - Codeforces][]

题意：

![7a287a1665eb4b0e801397d02468e4a7.png][]

![9449c09482f74be5947a3af89a5b2d64.png][]

![5737ae2839c94f41828cbca117227d45.png][]

思路：

首先K是1e18的范围，不能去枚举，那么就去考虑猜测结论

手推样例：

![cd920644b4054728bead48ca67798af4.jpeg][]

初步可以猜测，K应该取的是某个峰值

结论是，K应该取最小子段和的左端点

因为当前缀和遇到最小子段时，前缀和会变小。然后变成K的一条直线，遇到上升的子段时再上升

让K取最小子段和的左端点可以使变小的代价尽可能小

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N;
    int a[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int sum=0;
    	int ans=0;
    	int seg=0;
    	int mx=0;
    	for(int i=1;i<=N;i++){
    		sum+=a[i];
    		mx=max(mx,sum);
    		if(sum-mx<seg){
    			seg=sum-mx;
    			ans=mx;
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1845/problem/D
[7a287a1665eb4b0e801397d02468e4a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6f9493600d034626adf7aaf01d196871.png
[9449c09482f74be5947a3af89a5b2d64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f0576606bdb44d9cb344315b8c20098d.png
[5737ae2839c94f41828cbca117227d45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0cef29f752f240f2be619aeb7dd5e8da.png
[cd920644b4054728bead48ca67798af4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5704044296784b74986f60964e91fd1e.png