自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:26:42，当前版本为作者最后更新于2020-11-28 20:27:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P7107 题解

题意

构造两个长度为 $n$ 的数列 $x$ 和 $y$ ，使得：

• $\forall\ 1 \leq i \leq n,x_i+y_i=k$
• $\sum\limits_{i=1}^nx_i=k$
• 一共有且仅有 $p$ 个 $j$ 使得 $x_j=\max\limits_{i=1}^nx_i$

题解

先记 $\max\limits_{i=1}^nx_i=q$

首先，我们先考虑满足一共有 $p$ 个 $j$ 使得 $x_j=\max\limits_{i=1}^nx_i$ 这个条件，由于一共最多只能有 $p$ 个这样的最大值，于是我们可以得到这个最大值 $q \leq \min(m,k/p)$ ，再取大，就会导致 $pq>k$ ，不满足题意。

为了简化操作，我们直接让 $q=\min(m,k/p)$ 。

于是我们先让 $x_{1 \sim p}=q,y_{1 \sim p}=m-q$ 。

然后，我们定义 $rest=k-pq$ ，表示剩余有标记的纸团的个数，又要保证 $\max\limits_{i=p+1}^nx_i<q$ ，所以我们考虑在一定有解且 $rest>0$ 的情况下，剩下的 $x_i$ 取 $q-1$ 最合适。

当第 $h$ 个人取 $q-1$ 时， $rest-(q-1)<0$ ，那么直接把剩下所有的 $rest$ 都给这个 $h$ ，至此，所有有记号的纸条都已经分发完毕。

于是剩下的就直接取 $x_i=0$ ，即 $\forall\ h <i \leq n,x_i=0,y_i=m$ 。

至此，数列 $x$ 和 $y$ 就构造完毕了，而且复杂度也是 $\mathcal O(n)$ 的。

以上仅为有解情况，还需要考虑无解情况。

无解情况就是 $p$ 个 $q$ 分配完后所剩余的 $rest$ 分配给剩下的 $n-p$ 个人每人 $q-1$ 后仍有剩余，则我们是找不到这样的 $q$ 的。

用式子表示即为 $k-pq>(n-p)(q-1)$ 。

总的复杂度为 $\mathcal O(n)$ ，可以 $\colorbox{#52C41A}{\color{white}AC}$ 。

Code

代码因为加了注释比较长，文末有更简洁的代码。

// namespace Solution
const ll N = 100005;
ll x[N], y[N];

void check() {  // check
	ll sum = 0, cnt = 0;
	bool flag = 1;

	for (ll i = 1; i <= n; i++)
		sum += x[i], flag &= ((x[i] + y[i]) == m && (x[i] >= 0 && y[i] >= 0)), cnt += (x[i] == q);  // recount
	if (sum != k || !flag || cnt != p) {   // review
		puts("NO");
		exit(0);
	}
}

int main() {
	ll n = read(), m = read(), k = read(), p = read();   //   read
	ll q = min(m, k / p);    //   最大值

	if (k - q * p > (n - p) * (q - 1))    //    如果 分配完所有最大值 后 剩余的数分配给剩余的人 每个人 q-1 仍会有剩余
		return puts("NO"), 0;    //  无解

//  Case 1 - p max 
	for (ll i = 1; i <= p; i++)     //  这些 xi 都取最大值
		x[i] = q, y[i] = m - q;

//  Case 2 - n-p less
	bool fflag = 1;   //     用于记录是否剩余还可以分出 q-1
	ll rest = k - q * p;    //   rest 记录剩余的个数

	for (ll i = p + 1; i <= n; i++) {

		// Subcase 1 - q-1 ok
		if (fflag == true && rest >= q - 1)   //  judge
			x[i] = q - 1, rest -= q - 1;   //  赋值，且剩余减去 q-1

		// Subcase 2 - rest == 0 too little
		else if (rest <= 0)  // judge
			x[i] = 0;   //  0

		// Subcase 3 - still have , but not enough
		else
			x[i] = rest, rest = 0, fflag = 0;  //  get all the rest

		y[i] = m - x[i];   // set y
	}

// namespace Output
	puts("YES");

//	check();

	for (ll i = 1; i <= n; i++)
		write(x[i]), putchar(' '), write_endl(y[i]);  // output

	return 0;
}

更简洁一点的代码：

	ll n=read(),m=read(),k=read(),p=read();
	ll q=min(m,k/p);
	if(k-q*p>(n-p)*(q-1))return puts("NO"),0;
	for(ll i=1;i<=p;i++)x[i]=q,y[i]=m-q;
	bool ff=1;
	ll rs=k-q*p;
	for(ll i=p+1;i<=n;i++){
		if(ff==true&&rs>=q-1)x[i]=q-1,rs-=q-1;
		else if(rs==0)x[i]=0;
		else x[i]=rs,rs=0,ff=0;
		y[i]=m-x[i];
	}
	puts("YES");
	for(ll i=1;i<=n;i++)write(x[i]),putchar(' '),write_endl(y[i]);

后记

个人觉得算是半道模拟题

最后，祝洛谷月赛越办越好!
完结撒花~顺便求赞