JZTXT

Educational Codeforces Round 151 (Rated for Div. 2) D. Rating System

发布时间 2023-07-07 20:59:46作者: 突破铁皮

贪心

由题可得，对于k的选择一定是单调递增的，对于前面选定的k后面选的k必须大于之前选的才会发生新的变化，因此k的选择其实是一个单调栈，由前缀和组成

我们要想最后的结果最大，则k值一定要尽可能的高，例如当选中i为k值时，如果从i后面某个原本的前缀和要大于选k之后所得到的前缀和的话，说明k不是最优的

可以证明，假设选k为最优的，然后某个原本的前缀和为u,选k对应的前缀和为w，u>w,则在u这个位置如果选u的话，则后面的下限为u要大于k,因此k不是最优的，反之如果k是最优的，则保证了从k开始所有的u<=w

 

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,t;
void solve(){
	cin>>n;
	ll sum=0,k=0,ans=0;
	ll mx=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		sum+=x;
		mx=max(mx,sum);//单调递增 
		ans+=x;//选了对应k之后的值 
		if(ans<k) ans=k;
		if(ans<mx){//如果原值大于对应k的值，说明下限还可以增大 
			ans=mx;
			k=mx;
		}
		
	}
	cout<<k<<endl;
	
	
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
		cin>>t;
		while(t--){
		solve();
	}
}