洛谷1281 书的复制二分

题目链接:

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

题意:

题解:

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

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 500+10;
17 
18 int a[maxn],n,k;
19 
20 bool check(int x){
21     int s=n;
22     for(int i=k; i>=1; i--){
23         int res = x;
24         while(s>=1 && res>=a[s]) res -= a[s--];
25         if(s == 0) return true;
26     }
27     return false;
28 }
29 
30 void print(int T){
31     vector<pair<int,int> > ans;
32     int s=n,e=n;
33     for(int i=k; i>=1; i--){
34         int res = T;
35         e = s;
36         while(s>=1 && res>=a[s]) res -= a[s--];
37         ans.push_back(MP(s+1,e));
38     }
39     for(int i=(int)ans.size()-1; i>=0; i--){
40         printf("%d %d
",ans[i].first,ans[i].second);
41     }
42 }
43 
44 int main(){
45     int L=0,R=0;
46     cin >> n >> k;
47     for(int i=1; i<=n; i++){
48         cin >> a[i];
49         R += a[i];
50     }
51 
52     int T=0;
53     while(L <= R){
54         int mid = (L+R)/2;
55         if(check(mid)) T=mid,R=mid-1;
56         else L=mid+1;
57     }
58 
59     print(T);
60 
61     return 0;
62 }

洛谷1281 书的复制 二分

题目链接:

题意:

题解:

代码:

洛谷1281 书的复制二分