View Code of Problem 2594

/*之前一直想不通,明白了用时间二分来接近要求的值就清晰了
  迫近的值之后来判断哪个是成立的即可
*/


#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.


Back to problem 2594