# 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
代码因为加了注释比较长，文末有更简洁的代码。
```cpp
// 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;
}
```
更简洁一点的代码：
```cpp
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]);
```
## 后记
个人觉得算是半道模拟题
最后，祝洛谷月赛越办越好!
完结撒花~顺便求赞