二 分 板 子

标签： int sum cin long ans tie

#include "bits/stdc++.h"
#define int long long
using namespace std;
int a[100000],ans[100000];
int n;
int check(int mid)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		ans[i]=ceil(mid*1.0/a[i]);
		if(ans[i]<=0)
		ans[i]=1;
		if(ans[i]>1e9)
		ans[i]=1e9;
		sum+=ans[i];
	}
	for(int i=1;i<=n;i++)
	if(sum>=ans[i]*a[i])
	return 0;
	return 1;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
      cin>>n;
      for(int i=1;i<=n;i++)
      cin>>a[i];
      int l=0,r=1e12;
      while(l<r)
      {
      	int mid=(l+r+1)/2;
      	if(check(mid))  l=mid;
      	else r=mid-1;
	  }
	  if(check(l))
	  {
	  	for(int i=1;i<=n;i++)
	  	cout<<ans[i]<<' ';
	  	cout<<'\n';
	  }
	  else
	  cout<<"-1"<<'\n';
	}

}

Problem - C - Codeforces

标签：,int,sum,cin,long,ans,tie
From： https://blog.csdn.net/2301_80160438/article/details/140864769