做題思路

數列分段 Section IIhttps://www.luogu.com.cn/problem/P1182正如題目所說，我們需要得到一個最小的最大段的值，可能有人將注意力放在分段上，事實上，我們更多的應該關注結果。這是一道二分答案的題，你可以先確認某次分段后的可能的最大段的值q，然后盡量往最大段的值方向去分段，這樣，在保證了分段后的最大段的值小于等于q，再看所分的段數，如果大于限定的段數，說明不可能最大段的值是q。因為在保證所分段的值不超過q的情況下，無法減少段數使其達到要求，這時應該往大于q的范圍上去找。如果小于等于限定的段數，說明可能還有更小的q。因為段數小于要求，可以將某段拆成多段來增大段數，這時可能有更小的q符合要求。而這時為了更快的找到q的值，我們可以使用二分查找的方式去找。對于n個數，最小的q就是每個一段分出n段時，n個數中的最大值，最大的q就是只分出1段時，n個數的和。

#include<stdio.h>
#include<stdlib.h>
int check(int max,int *data,int num,int limit_count){int current_sum=0,count=0;for(int i=0;i<num;i++){if(data[i]>max)return 0;if(current_sum+data[i]>max){count++;current_sum=data[i];}else current_sum+=data[i];}count++;return count<=limit_count;
}
int main() {int N, M, max = 0, sum = 0;scanf("%d %d", &N, &M);int *data = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++) {scanf("%d", &data[i]);sum += data[i];if (data[i] > max)max = data[i];}int left=max,right=sum;while(left<right){int mid=(left+right)/2;if(check(mid,data,N,M))right=mid;else left=mid+1;}printf("%d",left);free(data);return 0;
}

書的復制https://www.luogu.com.cn/problem/P1281?這道題的思路和上面的題一模一樣，但要注意輸出時的條件：行的起始編號應該從小到大排列，如果有多解，則盡可能讓前面的人少抄寫。

#include<stdio.h>
#include<stdlib.h>
int check(int max,int *data,int num,int limit_count){int current_sum=0,count=0;for(int i=0;i<num;i++){if(data[i]>max)return 0;if(current_sum+data[i]>max){count++;current_sum=data[i];}else current_sum+=data[i];}count++;return count<=limit_count;
}
int main() {int N, M, max = 0, sum = 0;scanf("%d %d", &N, &M);int *data = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++) {scanf("%d", &data[i]);sum += data[i];if (data[i] > max)max = data[i];}int left=max,right=sum;while(left<right){int mid=(left+right)/2;if(check(mid,data,N,M))right=mid;else left=mid+1;}int result[M][2],current_sum=0,count=0;result[0][1]=N,result[M-1][0]=1;for(int i=N;i>0;i--){if(current_sum+data[i-1]>left){result[count++][0]=i+1;result[count][1]=i;current_sum=data[i-1];}else current_sum+=data[i-1];}for(int i=M-1;i>=0;i--){printf("%d %d\n",result[i][0],result[i][1]);}free(data);return 0;
}