第四题。
原题链接：https://www.luogu.org/problem/show?pid=1281#sub
借鉴了一篇题解的思路。
1 #include <cstring> 2 #include <cstdio> 3 #include <iostream> 4 #include <cmath> 5 #include <algorithm> 6 #define maxn 1005 7 using namespace std; 8 int n,m,book[maxn]; 9 int ans; 10 inline int read(){ 11 int num = 0; 12 char c; 13 bool flag = false; 14 while ((c = getchar()) == ' ' || c == ' ' || c == ' '); 15 if (c == '-') 16 flag = true; 17 else 18 num = c - '0'; 19 while (isdigit(c = getchar())) 20 num = num * 10 + c - '0'; 21 return (flag ? -1 : 1) * num; 22 } 23 bool check(int now){ 24 int ans=1; 25 int tot=0; 26 for(int i=n;i>=1;i--){ 27 if(tot + book[i] > now){ 28 tot = book[i]; 29 ans++; 30 } 31 else 32 tot += book[i]; 33 } 34 if (ans > m) 35 return false; 36 else 37 return true; 38 } 39 int main(){ 40 n = read();m = read(); 41 int l=0;int r =0; 42 for(int i=1;i<=n;i++){ 43 book[i] = read(); 44 r += book[i]; 45 } 46 while(l < r){ 47 int mid=(l+r) >> 1; 48 if(check(mid)) 49 r=mid; 50 else 51 l=mid+1; 52 } 53 ans = l; 54 int out[maxn][2]; 55 int cnt = n; 56 int now = ans; 57 for(int i=m;i>=1;i--){ 58 out[i][2] = cnt; 59 while(now - book[cnt] >= 0){ 60 now -= book[cnt--]; 61 if(cnt == 0) 62 break; 63 } 64 out[i][1] = cnt + 1; 65 now = ans; 66 } 67 for(int i=1;i<=m;i++) 68 printf("%d %d ",out[i][1],out[i][2]); 69 return 0; 70 }