tips:
1.用条件判断左右区间该怎么更新
2.答案在区间范围内是否是整数变化
3.这个区间变换还是没有搞的太懂
4.二分超时的原因是二分的区间更新写错了
5.最大化最小值??
//二分超时很大一部分原因是二分时陷入了死循环///blog/1446986///helica/p/5173800.html#include<cstdio>using namespace std;const int MM=100010;int a[MM];int n,m;int L,R;int summ;int judge(int x){int ans=1;int sum=0;for(int i=0;i<n;i++){if(sum+a[i]<=x){sum+=a[i];}else{ans++;sum=a[i];}}//ans=summ/x;return ans;}int main(){while(scanf("%d%d",&n,&m)!=EOF){int tmp=0;R=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]>tmp){tmp=a[i];}R+=a[i];}L=tmp;summ=R;while(L<R){//等于的话不用判断,确定了唯一的位置int mid=L+(R-L)/2;if(judge(mid)<=m){R=mid-1;}else{L=mid+1;}}printf("%d\n",L);}return 0;}
View Code
6.还可以不对 ==号进行处理---解决模糊问题?比如说5.
//二分超时很大一部分原因是二分时陷入了死循环///blog/1446986///helica/p/5173800.html#include<cstdio>using namespace std;const int MM=100010;int a[MM];int n,m;int L,R;int summ;int judge(int x){int ans=1;int sum=0;for(int i=0;i<n;i++){if(sum+a[i]<=x){sum+=a[i];}else{ans++;sum=a[i];}}//ans=summ/x;return ans;}int main(){while(scanf("%d%d",&n,&m)!=EOF){int tmp=0;R=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]>tmp){tmp=a[i];}R+=a[i];}L=tmp;summ=R;while(L<R){//等于的话不用判断,确定了唯一的位置int mid=L+(R-L)/2;if(judge(mid)<m){R=mid-1;}if(judge(mid)>m)L=mid+1;}}printf("%d\n",L);}return 0;}
View Code