题解 P6775 【[NOI2020]制作菜品】

· · 题解

随机化跑得飞快

总共300ms，还没开O2，全站第一，第二600+ms！

Case1：m=n-1

必然有解，贪心拿最小的与最大的匹配即可。

由抽屉原理，最小的d_i \leq k，最大的d_i \geq k，于是两两匹配，匹配后m仍然等于n-1，由归纳法可得有解。

Case2：m>n-1

随便匹配，直至m=n-1后使用Case1做法即可。

Case3：m=n-2

就是划分为两个集合，使\sum(d_i-k)=-k，可以bitset优化背包。但是复杂度四亿......

于是，伟大的随机化横空出世

但是直接随机会WA惨，或者被构造数据卡死。

令p_i=|d_i-k|，则两个集合的\sum p_i相等，那就很好办了。一开始只选一个数，如果目前被选中数的p_i和小于所有p_i和的一半，就随机加入一个数，否则随机删除一个数，随机4nk次亲测可以通过。

得到一个集合的划分后，将两个集合的负数对调就可以得出一组解。

证明：

充分性：设划分出集合S_1的正数和为p，负数和为q，集合S_2中正数和为x，负数和为y，则有：

\sum_{i \in S_1}p_i=p-q=x-y=\sum_{i \in S_2}p_i

所有p_i总和为p-q+x-y。

所以：

p-q=x-y=\frac{p-q+x-y}{2}

把两个集合p_i中的负数对调，再全部换成去绝对值，设最后集合为T_1，T_2，则有：

\sum_{i \in T_1}(d_i-k)=p+y \sum_{i \in T_2}(d_i-k)=q+x

因为所有d_i和为-2k，而且p+y=q+x，所以集合T_1中所有数之和为-k，满足有解条件。

必要性：设划分出集合S_1中对应到最终集合T_1后d_i>k的有n_1个，d_i<k的有n_2个，对于另一个集合S_2，对应到T_2，则为m_1个和m_2个，d_i=k的不造成影响，故可以忽略。

调换负数前：

\sum_{i \in S_1}p_i=(n_2-n_1)k+\sum_{i \in T_1,d_i>k}d_i-\sum_{i \in T_1,d_i<k}d_i \sum_{i \in S_2}p_i=(m_2-m_1)k+\sum_{i \in T_2,d_i>k}d_i-\sum_{i \in T_2,d_i<k}d_i

调换负数后：

\sum_{i \in T_1}(d_i-k)=\sum_{i \in S_1,d_i>k}d_i+\sum_{i \in S_2,d_i<k}d_i-(n_1+m_2)k \sum_{i \in T_2}(d_i-k)=\sum_{i \in S_2,d_i>k}d_i+\sum_{i \in S_1,d_i<k}d_i-(n_2+m_1)k

因为T_1中d_i-k和与T_2中d_i-k和相等，即以上两式相等，所以：

\sum_{i \in S_1,d_i>k}d_i+\sum_{i \in S_2,d_i<k}d_i-(n_1+m_2)k=\sum_{i \in S_2,d_i>k}d_i+\sum_{i \in S_1,d_i<k}d_i-(n_2+m_1)k \sum_{i \in S_1,d_i>k}d_i-\sum_{i \in S_1,d_i<k}d_i+(n_2-n_1)k=\sum_{i \in S_2,d_i>k}d_i-\sum_{i \in S_2,d_i<k}d_i+(m_2-m_1)k \sum_{i \in S_1}p_i=\sum_{i \in S_2}p_i

证毕。

复杂度降至一亿，而且跑出一组解就会直接退出，常数也不大。

代码并不难写：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,k;
struct B{
    int id,wei,val;
}a[500],b[500];
void f(int l,int r)
{
    int mn=-1,mx=-1;
    for(int i=l;i<=r;i++)
        if(mn==-1||b[i].wei<b[mn].wei)
            mn=i;
    swap(b[l],b[mn]);
    for(int i=l;i<=r;i++)
        if(mx==-1||b[i].wei>b[mx].wei)
            mx=i;
    swap(b[r],b[mx]);
    return;
}
void solve(int l,int r)
{
    if(l==r) return;
    if(l+1==r){
        if(b[l].wei==0) printf("%d %d\n",b[r].id,k);
        else if(b[r].wei==0) printf("%d %d\n",b[l].id,k);
        else printf("%d %d %d %d\n",b[l].id,b[l].wei,b[r].id,b[r].wei);
    }
    else{
        f(l,r);
        printf("%d %d %d %d\n",b[l].id,b[l].wei,b[r].id,k-b[l].wei);
        b[r].wei-=k-b[l].wei;
        solve(l+1,r);
    }
    return;
}

#include<ctime>
#include<cstdlib>
int find(void)
{
    int sum=0,pos=1;
    for(int i=0;i<n;i++){
        a[i].wei=b[i].wei-k; a[i].id=b[i].id;
        a[i].val=max(a[i].wei,-a[i].wei);
        sum+=a[i].val;
    }
    srand(time(NULL));
    int tar=sum>>1,lim=4*n*k,Now=a[0].val;
    while(lim--){
        if(Now==tar) break;
        if(Now>tar){
            int t=rand()%pos;
            Now-=a[t].val; swap(a[t],a[--pos]);
        }
        else{
            int t=rand()%(n-pos)+pos;
            Now+=a[t].val; swap(a[t],a[pos++]);
        }
    }
    if(lim<0) return -1;
    int l=0,r=n;
    for(int i=0;i<pos;i++)
        if(a[i].wei>=0) b[l++]=a[i];
        else b[--r]=a[i];
    for(int i=pos;i<n;i++)
        if(a[i].wei>=0) b[--r]=a[i];
        else b[l++]=a[i];
    for(int i=0;i<n;i++)
        b[i].wei+=k;
    return l;
}

void z(void)
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&b[i].wei);
        b[i].id=i+1;
    }
    while(m>=n){
        f(0,n-1); m--;
        printf("%d %d\n",b[n-1].id,k);
        b[n-1].wei-=k;
    }
    if(m==n-1) solve(0,n-1);
    else{
        int p=find();
        if(p==-1){
            printf("-1\n");
            return;
        }
        solve(0,p-1); solve(p,n-1);
    }
    return;
}
int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) z();
    return 0;
}