http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1364
【题意】：把n分为 均分为m 段 每段n/m个数字 每段可以选一个最大的数 求这些数相加起来>k 的最小的m
一开始的 rmq+二分的想法是错误的 因为并不是分的越多的段数 得到的 结果就会越大
例如 1 2 9 9 2 2 分成两份得到的结果比分成三段的更大 所以分成的段数与结果之间不存在单调性 不能用二分
不能用二分只能 将段数由小到大枚举 但是这里有一个 技巧 可以很大的缩短时间：
当分成i段得到的段长L1 与 之前分成 i-1段得到的段长相同 那就只要把前一次的结果再加上这一次 第i段的最大值 就是当前的结果了 这一步少做了很多步骤 节约了很多时间
ac代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<math.h> using namespace std; int n,a[200002],d[200002][30],k; void init() // 从点i开始 长1<<j 的最大值 { for(int i=1; i<=n; i++) d[i][0]=a[i]; for(int j=1; (1<<j)<=n; j++) for(int i=1; i+(1<<j)-1<=n; i++) d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]); } int rmq(int x,int y) { int k=0; while(1<<(k+1)<=y-x+1) k++; return max(d[x][k],d[y-(1<<k)+1][k]); } int solve() { int prev=-1,sum,j,left,right; for(int i=1;i<=n;i++)//段数 { int l=n/i; if(prev!=l) // { j=1;sum=0; } while(j<=i) { left=(j-1)*l+1; right=j*l; sum+=rmq(left,right); if(sum>k) return i; j++; } prev=l; } return -1; } int main() { int i,j,m,t; while(scanf("%d%d",&n,&k)) { if(n==-1&&k==-1) break; for(int i=1; i<=n; i++) scanf("%d",&a[i]); init(); printf("%d ",solve()); } return 0; }
二分时的错误代码 500多ms 时wa
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<math.h> using namespace std; int n,a[200002],d[200002][30],k; void init() // 从点i开始 长1<<j 的最大值 { for(int i=1; i<=n; i++) d[i][0]=a[i]; for(int j=1; (1<<j)<=n; j++) for(int i=1; i+(1<<j)-1<=n; i++) d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]); } int rmq(int x,int y) { int k=0; while(1<<(k+1)<=y-x+1) k++; return max(d[x][k],d[y-(1<<k)+1][k]); } int solve() { int ans; int left=1,right=n;int m,l,r; int best=n+1; while(left<right) { int i; i=(left+right)/2; // mid m=n/i; //分为i段 每段m个人 ans=0; for(int j=1; j<=i; j++) { l=(j-1)*m+1; r=j*m; // printf("l %d r %d zhi %d ",l,r,rmq(l,r)); ans+=rmq(l,r); } if(ans>k) { if(best>i) best=i; right=i-1; } else left=i+1; } if(best>n) return -1; return best; } int main() { int i,j,m,t; while(scanf("%d%d",&n,&k)) { if(n==-1&&k==-1) break; for(int i=1; i<=n; i++) scanf("%d",&a[i]); init(); printf("%d ",solve()); } return 0; }