P9380 题解

· · 题解

数据范围非常小。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;
}