PKU 1064 Cable master
http://poj.org/problem?id=1064
N本のケーブルの長さが実数で与えられる。
これを等しい長さのK本のケーブルに分けたい。
分けられる長さの最大値を求めろというような問題。
ただの二分探索だと思って実数でやるとなぜかWAが出て、0.00を出力しないといけない条件を見落としていたので、それを付け加えてもWA。
仕方ないので、整数にして扱うことにして、しばらくデバッグ出力を出したままにしていたり、足し算で桁あふれしていたりでWAと戦った末に何とかAC。
簡単そうなのに、いろいろとはまりました。
int in[10000]; main(){ int n,k; scanf("%d%d",&n,&k); ll u=0,l=0; rep(i,n){ int it,du; scanf(" %d.%d",&it,&du); in[i]=it*100+du; u+=in[i]; } if(u<k){ printf("0.00\n"); return 0; } ++u; while(l+1<u){ ll mid=(u+l)/2; ll t=0; rep(i,n)t+=in[i]/mid; if(t<k)u=mid; else l=mid; } printf("%d.%02d\n",(int)(l/100),(int)(l%100)); }