洛谷1281 书的复制 二分

题目链接:

https://www.luogu.org/problem/show?pid=1281

题意:

题解:

二分法+贪心。 二分最大时间t贪心判断t是否可行，求出最小时间T。 贪心构造解：从后向前尽量分配给靠后的人更多的书。

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 500+10; int a[maxn],n,k; bool check(int x){ int s=n; for(int i=k; i>=1; i--){ int res = x; while(s>=1 && res>=a[s]) res -= a[s--]; if(s == 0) return true; } return false; } void print(int T){ vector<pair<int,int> > ans; int s=n,e=n; for(int i=k; i>=1; i--){ int res = T; e = s; while(s>=1 && res>=a[s]) res -= a[s--]; ans.push_back(MP(s+1,e)); } for(int i=(int)ans.size()-1; i>=0; i--){ printf("%d %d\n",ans[i].first,ans[i].second); } } int main(){ int L=0,R=0; cin >> n >> k; for(int i=1; i<=n; i++){ cin >> a[i]; R += a[i]; } int T=0; while(L <= R){ int mid = (L+R)/2; if(check(mid)) T=mid,R=mid-1; else L=mid+1; } print(T); return 0; }