mysterious 二分加贪心
/*好题啊！在比赛的时候光想贪心了。没想到二分。结果悲剧了。二分天数有一个注意点就是边界的控制，要选文n，而不是10000，因为数组a后面有很多的空白。二分的条件是用价钱来控制。将7天为一个周期，来进行控制。具体见代码。*/#include <stdio.h>#include <cstring>int a[10001][51];int n,m,b;int sum[8];bool cal(int t){ int count=0; memset(sum,0,sizeof(sum)); for(int k=1; k<=7&&k<=t; k++) { int min=100000; for(int j=1; j<=m; j++) { int summ=0; for(int i=k; i<=t; i+=7) { summ+=a[i][j]; } if(summ<min) min=summ; } sum[k]=min; count+=sum[k]; } if(count<=b) return true; else return false;}int erfen(){ int low=1,high=n,mid=0,res=-1; while(low<=high) { mid=(high+low)/2; if(cal(mid)) { res=mid; low=mid+1; } else high=mid-1; } return res;}int main(){ while(scanf("%d%d%d",&n,&m,&b)==3) { for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&a[i][j]); printf("%d\n",erfen()); } return 0;}