77分求条,TLE on#4 #9
  • 板块P1281 书的复制
  • 楼主c22040
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/3 19:52
  • 上次更新2025/7/4 06:28:10
查看原帖
77分求条,TLE on#4 #9
1040533
c22040楼主2025/7/3 19:52
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N],l[N],r[N];
bool check(int k){
	int js=0;
	for(int i=n;i>=1;i--){
		int sum=0,beg=i;
		while(sum+a[beg]<=k&&beg>=1){sum+=a[beg];beg--;}
		i=beg+1;js++;
	}
	return js<=m;
}
int find(int l,int r){
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	return  l;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int k=find(1,N);
	int js=0;
	for(int i=n;i>=1;i--){
		int sum=0,beg=i;
		while(sum+a[beg]<=k&&beg>=1){sum+=a[beg];beg--;}
		js++;
		l[js]=beg+1;r[js]=i;
		i=beg+1;
	}
	for(int i=js;i>=1;i--)cout<<l[i]<<' '<<r[i]<<'\n';
	return 0;
}
2025/7/3 19:52
加载中...