深信服笔试M卷最后一天 10.11

编程题第四题

题意

一个n长度的数组，保留k个数，不改变原来顺序，分成两段，小明负责前一段(总和为s1)，小白负责后一段(总和为s2)，

求min(max(s1,s2));

一开始直接打了个暴力，直接删除最大的n-k个数，过60%。之后一直在想正解，二分答案，但check函数不知道怎么写。

完了之后才有一点点思路，大概双指针，用两个set存两段数组，哪边小就往哪边加数。不知道这个思路对不对，有没有大佬看一下

int n,m,k;
int a[N];
bool check(int x,int k){
	set<int> st1,st2;
	int s1=0,s2=0,l=1,r=n;
	while(l<r){
		if(s1<=s2){
			st1.insert(a[l]);
			s1+=a[l++];
			if(s1>x){
				if(k==0) return false;
				s1-=*st1.rbegin();
				st1.erase(*st1.rbegin());
				k--;
			}
		}
		else{
			st2.insert(a[r]);
			s2+=a[r--];
			if(s2>x){
				if(k==0) return false;
				s2-=*st2.rbegin();
				st2.erase(*st2.rbegin());
				k--;
			}
		}
	}
	return true;
}

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l = 0,r=1e18;
	while(l<r){
		int mid = (l+r)/2;
		if(check(mid,n-k)) r = mid;
		else l = mid+1;
	}
	cout<<l<<endl;
}