/*之前一直想不通,明白了用时间二分来接近要求的值就清晰了 迫近的值之后来判断哪个是成立的即可 */ #include<stdio.h> #define ll long long int #define MAX 100005 int b; int m[1005]; int num=0; int n; ll geshu(int n) { ll ans=0; int i; for(i=0;i<b;i++) ans+=(n-1+m[i])/m[i]; return ans; } int main() { int t; scanf("%d",&t); while(t--) { int i; scanf("%d%d",&b,&n); for( i=0;i<b;i++) scanf("%d",&m[i]); int lt=0,rt=MAX*n; while(lt<rt) { int mid=(lt+rt)/2; if(geshu(mid)<n) lt=mid+1; else rt=mid; } int flag; flag=geshu(lt-1); int wtf=0; for(i=0;i<b;i++) { if((lt-1)%m[i]==0) { flag++; if(flag==n) { wtf=i+1; break; } } } printf("Case #%d: %d\n",++num,wtf); } return 0; } |
Double click to view unformatted code.