#4,#8,#15,#16过不了
查看原帖
#4,#8,#15,#16过不了
1233392
RY111楼主2024/7/14 11:56

无解应该怎么爬判断呢,这样直接判断是否为边界好像不行

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int l,k;
int a[maxn];
bool check1(int mid) {
	int sum=0;
	int cnt=0;
	for(int i=1; i<=l; i++) {

//	{cout<<"sum和mid"<<sum<<" "<<mid<<endl;
//	cout<<a[i]<<endl;
		if(a[i]>0) {
			sum+=a[i];
			if(sum>=mid) {
				sum=0;
				cnt++;

			}

		}

		else if(a[i]<0) {
			if(sum+a[i]<0) {
				sum=0;

			} else if(a[i]+sum>0) {
				sum+=a[i];

			}


		}
	}
//	cout<<cnt<<endl;
	return cnt<=k?true:false;
}
bool check2(int mid) {
	int sum=0;
	int cnt=0;
	for(int i=1; i<=l; i++) {
		if(a[i]>0) {
			sum+=a[i];
			if(sum>=mid) {
				sum=0;
				cnt++;

			}

		}

		else if(a[i]<0) {
			if(sum+a[i]<0) {
				sum=0;

			} else if(a[i]+sum>0) {
				sum+=a[i];

			}


		}
	}
	return cnt>=k?true:false;
}
int bs1(int l,int r) {
	while(l<r) {
		int mid=(l+r)/2 ;

//		cout<<"mid="<<mid<<endl;
		if(check1(mid))
			r=mid;
		else
			l=mid+1;
	}
	return l;
}
int bs2(int l,int r) {
	while(l<r) {
		int mid=(l+r+1)/2 ;
		if(check2(mid))
			l=mid;
		else
			r=mid-1;
	}
	return l;
}
signed  main() {
	cin>>l>>k;
	for(int i=1; i<=l; i++) {
		cin>>a[i];
	}
	if(bs1(1,1e18+1)==1||bs2(-1,1e18+1)==1e18+1)
		cout<<"-1";
	else
		cout<<bs1(1,1e18+1)<<" "<<bs2(1,1e18+1);


	return 0;
}
2024/7/14 11:56
加载中...