P8948题解

题意简述

两场考试满分 $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$、$B$ 由你的输出决定，等于各自那列的最大值。第 $1$ 人 $c_1=2000$，两场都满，故 $a_1=A$、$b_1=B$，可自行指定 $A$、$B$。

关键是消掉四舍五入。取 $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)$。

参考代码

279 Bcpp

#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;
}