OI - 制作菜品(NOI 2020) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 制作菜品(NOI 2020)

发表于 分类于 Valine：

贪心是一种很早就学了但是直到最后还是可能做不出来的算法

# 题面

> Linked 洛谷 P6775

# 解析

线上赛的时候就注意到 $m\ge n-2$ 有鬼……但是还是没想出来。既然是贪心，就会涉及到一大堆证明。按照部分分一步步推导：

# Part1 - $m=n-1$

先把 $\{d_i\}$ 从小到大排序。

定理 1

若 $m=n-1$，则 $d_1< k$。

若 $d_1\ge k$，则 $d_i\ge d_1\ge k$，$\sum d_i\ge nk> (n-1)k=mk$；但是 $\sum d_i=mk$，矛盾。

定理 2

若 $m=n-1$ 且 $n>2$，则 $d_1+d_n> k$。

仍然反证，若 $d_1+d_n\le k$，则有 $d_i\le d_n< k$，$d_2+d_3+\dots+d_{n-1}+(d_1+d_n)< (n-1)k=mk$，与 $\sum d_i=mk$ 矛盾。

这意味着什么？对于 $m=n-1$ 的情况：

  1. 若 $n>2$ 则直接找到最大和最小、把最小用完、再拿大的补，这样一定可以有合法的方案；并且递归到 $m’=m-1,n’=n-1$ 的情况——因为做出了一道菜（m--），而且最小的用完了（n--），注意到因为 $d_1+d_n>k$，所以最大的不会用完。
  2. 若 $n=2$ 直接两个匹配。

# Part2 - $m>n-1$

定理 3

若 $m>n-1$，则 $d_n\ge k$。

因为 $m,n$ 是整数，条件相当于 $m\ge n$。

和定理1证明很像，若 $d_n< k$ 则 $d_i\le d_n< k$，$\sum d_i< nk\le mk$，与 $\sum d_i=mk$ 矛盾。

对于这种情况，可以先只用最大的 $d_n$ 做出一道菜，则归入 $m’=m-1$ 的子问题；注意到有可能 $k\mid d_n$，此时 $d_n$ 可能用完，需要归入 $n’=n-1$ 的子问题。

直到 $m=n-1$，一定有解。

# Part3 - $m=n-2$

定理 4

当 $m=n-2$ 时，$\{d_i\}$ 能被划分为两个集合 $S_1,S_2$ 使得 $(|S_1|-1)k=\operatorname{sum}(S_1)$ 且 $(|S_2|-1)k=\operatorname{sum}(S_2)$ 是有解的充要条件。

其实就是把 $m=n-2$ 划分成两个 $m=n-1$ 的问题求解。如果能划分出来，那么一定有解（充分性）；接下来要证明有解的情况一定可以划分出来（必要性）。

这里比较巧妙的一种一种理解是建图——若一个菜用了两个食材 $a,b$，则连边 $(a,b)$。

在 $m=n-1$ 的问题中，最后一步操作用完了两个食材做出了一道菜。此时 $m’=m-1,n’=n-2$，则 $n,m$ 之间的差减少 $1$，在此之前只有“用完最小值和部分最大值”，$m’=m-1,n=n-1$，$m,n$ 差值不变。

综上，一个 $m=n-1$ 的子问题会让 $m,n$ 差值减少 $1$。

而问题最后要让 $m=n=0$，则 $m,n$ 的差值在操作过程中必须减二，也就对应了两个 $m=n-1$ 的问题。

划分可以背包，$f_{i,S}$ 表示前 $i$ 个 $d_i$，选择了一个非空子集 $T$（正因为是非空，所以一开始就把 $d_1$ 固定选在 $T$ 内），有 $S=\sum_{i\in T}(k-d_i)$，是否存在方案。

因为是 bool 类，所以可以用 bitset 优化，而判断是否有解只需要看 $f_{n,k}$。

最后再用背包问题求一个可行解的方法来找到合法的划分，做两次 $m=n-1$ 的问题。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*Lucky_Glass*/
#include<cassert>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}

const int N=505,K=5005;
#define cs const int &

int n,m,k;
int num[N],id[N];
int nA,A[N],nB,B[N];
bitset<N*K*2> f[N];

bool cmp(cs a,cs b){return num[a]<num[b];}
void Print(int n,int m,int *id){
	int vn=n;
	for(int i=n;i>=1 && m>vn-1;i--){
		while(num[id[i]]>=k && m>vn-1)
			num[id[i]]-=k,printf("%d %d\n",id[i],k),m--;
		if(!num[id[i]]) vn--;
	}
	while(m){
		int mni=-1,mn=k,mxi=-1,mx=0;
		for(int j=1;j<=n;j++){
			if(num[id[j]]>mx) mxi=id[j],mx=num[id[j]];
			if(num[id[j]] && num[id[j]]<mn) mni=id[j],mn=num[id[j]];
		}
		printf("%d %d %d %d\n",mxi,k-mn,mni,mn);
		num[mxi]-=k-mn,num[mni]-=mn;
		m--;
	}
}
int main(){
	for(int cas=Read();cas;cas--){
		n=Read(),m=Read(),k=Read();
		for(int i=1;i<=n;i++) num[i]=Read(),A[i]=i;
		if(m>=n-1) Print(n,m,A);
		else{
			if(n==3){
				printf("-1\n");
				continue;
			}
			f[1]=f[0];
			f[1].set(N*K+k-num[1],1);
			for(int i=2;i<=n;i++){
				f[i]=f[i-1];
				if(k>num[i]) f[i]|=(f[i-1]<<(k-num[i]));
				else f[i]|=(f[i-1]>>(num[i]-k));
			}
			if(f[n].test(N*K+k)==0) printf("-1\n");
			else{
				int now=N*K+k;
				nA=nB=0;
				for(int i=n;i>=2;i--){
					if(f[i-1].test(now-(k-num[i])))
						now-=(k-num[i]),A[++nA]=i;
					else B[++nB]=i;
				}
				A[++nA]=1;
				int tot=0;
				for(int i=1;i<=nA;i++) tot+=num[A[i]];
				//assert(tot==(nA-1)*k);
				tot=0;
				for(int i=1;i<=nB;i++) tot+=num[B[i]];
				//assert(tot==(nB-1)*k);
				Print(nA,nA-1,A);
				Print(nB,nB-1,B);
			}
		}
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 零和 Zero-Sum-Bilibili