题解：P8948 [YsOI2022] NOIp 和省选
lailai0916
·
·
题解
题意简述
两场考试满分 400、600。设两场最高分为 A,B，第 i 人标准得分 c_i=\operatorname{round}\left(1000\left(\frac{a_i}{A}+\frac{b_i}{B}\right)\right)。已知 n 与所有 c_i（c_1=2000，其余在 [10,1990]），构造任意一组合法原始分 a_i\in[0,400]、b_i\in[0,600]。
解题思路
关键是消掉四舍五入。取 $A=200$、$B=500$，则
$$
c_i=1000\left(\frac{a_i}{200}+\frac{b_i}{500}\right)=5a_i+2b_i.
$$
右端恒为整数，舍入不再起作用，只需解方程 $5a_i+2b_i=c_i$，且 $a_i\in[0,200]$、$b_i\in[0,500]$。
由 $b_i=\frac{c_i-5a_i}{2}$，要求 $c_i-5a_i$ 为非负偶数且不超过 $1000$。两个条件确定 $a_i$：
1. 方程两边对 $2$ 取模，得 $a_i\equiv c_i\pmod 2$。
2. 由 $b_i\le 500$ 得 $a_i\ge\frac{c_i-1000}{5}$。
取满足下界的最小整数 $a_i=\max\left(0,\left\lceil\frac{c_i-1000}{5}\right\rceil\right)$，整数写法为 $\max\left(0,\lfloor(c_i-996)/5\rfloor\right)$。若其奇偶与 $c_i$ 不符则加 $1$，再令 $b_i=\frac{c_i-5a_i}{2}$。
可验证如此得到的 $a_i\le 198$、$b_i\le 500$，故第 $1$ 人的 $a_1=200$、$b_1=500$ 恰为两列最大值，$A=200$、$B=500$ 成立，构造自洽。
时间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,c;
cin>>n>>c;
cout<<"200 500\n";
for(int i=2;i<=n;i++)
{
cin>>c;
int a=max(0,(c-996)/5);
if((a^c)&1)a++;
cout<<a<<' '<<(c-5*a)/2<<'\n';
}
return 0;
}
```