25.5.20学习总结

做题思路

数列分段 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;
}