题解：P15083 [ICPC 2024 Chengdu R] Recover Statistics

· · 题解

题解：P15083 [ICPC 2024 Chengdu R] Recover Statistics

思路

注意到题目有一句话：

然而，这些值不存在有效的 P95 或 P99，因为 6×95\% 和 6×99\% 不是整数。

这启示我们，n 必须是 100 的倍数才能使这三个百分比为整数。为了方便，我们选择 n=100 来构造，这样就变成了：构造一个长为 100 的数列，使得有 50 个数均 \le a，有 95 个数均 \le b，有 99 个数均 \le c。

又注意到，有 a \lt b \lt c，所以 \le b 的数中包含 \le a 的，同时 \le c 的数中也包含 \le b 的。把前面的数代入一下，再减去重合部分，就会发现是 50 个数 \le a，a \lt 45 个数 \le b，b \lt 4 个数 \le c，还有一个数 \gt c。

既然已经限定 a \lt b \lt c，那么我们不用特判无解的情况，可以直接输出 50 个 a，45 个 b，4 个 c，还有一个 c+1，符合题目的约束条件。

完整代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a,b,c;
    cin>>a>>b>>c;
    cout<<"100\n";
    for(int i=1;i<=50;i++)//50个小于等于a的数
    {
        cout<<a<<' ';
    }
    for(int i=1;i<=45;i++)//95个小于等于b的数
    {
        cout<<b<<' ';
    }
    for(int i=1;i<=4;i++)//99个小于c的数
    {
        cout<<c<<' ';
    }
    cout<<c+1;//还有一个大于c的数
    return 0;
}