自动搬运

查看原文

来自洛谷，原作者为

	I_will_AKIOI 吾日三省吾身：洛谷等级分 2145 乎？CF Rating 1927 乎？AT 1724 乎？

搬运于2025-08-24 22:47:50，当前版本为作者最后更新于2023-12-19 21:11:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数据范围非常小。$N\le100,L\le6$，所以我们用枚举做。

枚举一下 $1\sim 10^L$ 的所有数，然后判断一下是否成立。

考虑将枚举出的 $K$ 乘以 $P_i$，发现全部是整数就得到答案。但是，由于 C++ 的特性，会被卡精度。

所以我们换一种思路做。由于 $P_i$ 表示一个比例，所以 $D_i=P_i\times K$。再判断其是否符合 $P_i-\frac{1}{2}\times 10^{-L}\le\frac{D_i}{K}< P_i+\frac{1}{2}\times 10^{-L}$ 即可。

读入比较麻烦，我们需要先读入字符串获取位数。一行的长度 $-2$ 就是 $L$。然后再找到小数点，两边就分别是整数和小数了。

#include<bits/stdc++.h>
using namespace std;
int n,l;
double inf,a[101],f[10]={1,0.1,0.01,0.001,0.0001,0.00001,0.000001};
bool check(int k)
{
  int sum=0;
  for(int i=1;i<=n;i++)
  {
  	int w=a[i]*k+0.5;
	if(a[i]-inf>(double)w/double(k)||(double)w/double(k)>=a[i]+inf) return 0;//不符合要求，退出
	sum+=w;
  }
  return sum==k;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)//读入浮点数
  {
  	string s;
  	cin>>s;
  	l=s.size()-2;
  	if(s[0]=='0') a[i]=0;
  	else a[i]=1;
  	for(int j=2;j<s.size();j++) a[i]+=f[j-1]*(s[j]-48);//枚举每一位的小数
  }
  inf=f[l]*0.5;
  for(int i=1;i<=1000000;i++) if(check(i)) {cout<<i;break;}
  return 0;
}