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]);

后记

个人觉得算是半道模拟题

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