PKU 3388 Japanese Puzzle

PKU

http://poj.org/problem?id=3388

n*nの正方形をk種類のピースを使って埋める。
このとき、最初の何行かを全く同じピース構成にしたい。
最大何行を同じ構成にできるか求めろというような問題


二分探索する。

int in[50000];

main(){
  int n,k;
  scanf("%d%d",&n,&k);
  rep(i,k) scanf("%d",in+i);
  int low=1,up=n+1;
  while(low+1<up){
    int mid=low+up>>1;
    int su=0;
    rep(i,k) su += in[i]/mid;
    if(su>=n) low=mid;
    else up=mid;
  }
  cout << low << endl;
  int cnt=0;
  rep(i,k){
    while(in[i]>=low && cnt<n){
      cout << i+1 << endl;
      in[i] -= low;
      ++cnt;
    }
  };
}