【题解】ATCoder_abc123_D - Cake 123_atcoder 每次给数组中的一个元素加一,动态维护数组中的最大值

Link: D - Cake 123

Description:

现有3种蛋糕，每个蛋糕都有一个称为美味度的整数值，如下所示：

• 第一种蛋糕的美味度是 
• 第二种蛋糕的美味度是 
• 第三种蛋糕的美味度是 

现要求买三个蛋糕，每种蛋糕各一个，显然共有种方法，对其按照美味度总和降序排列。输出前  种方法的蛋糕美味度总和。

Constraints:

• 
• 
• 

---

Analysis_1: 

• 无脑暴力枚举后排序，显然复杂度爆爆爆！，故考虑如何优化。分析数据规模，注意到的范围最大才 3000，故可以尝试枚举前两种蛋糕的所有组合，取前  种，再用这  种进一步和第三种蛋糕去组合，再取前  种即可。
• 

Sulution_1:

vector<ll> a,b,c;
 
int main() {
	int x,y,z,K; 
	cin >> x >> y >> z >> K;
	for(int i=0;i<x;i++) {
		ll t; cin >> t;
		a.push_back(t);
	}
	for(int i=0;i<y;i++) {
		ll t; cin >> t;
		b.push_back(t);
	}
	for(int i=0;i<z;i++) {
		ll t; cin >> t;
		c.push_back(t);
	}
	//处理前两种组合
	vector<ll> ab;
	for(int i=0;i<x;i++) {
		for(int j=0;j<y;j++) {
			ab.push_back(a[i]+b[j]);
		}
	}
	sort(ab.begin(),ab.end(),greater<ll>());
    // 取前K种和第三种组合，注意前两种若不够K，要取min
	vector<ll> ans;
	for(int i=0;i<min(K,x*y);i++) {
		for(int j=0;j<z;j++) {
			ans.push_back(ab[i]+c[j]);
		}
	}
	sort(ans.begin(),ans.end(),greater<ll>());
	for(int i=0;i<K;i++) cout << ans[i] << endl;
	return 0;
}

Analysis_2: 

• 如果把每种蛋糕分别排序呢？每次按美味度最大的依次取出，可以保证一定在前  种，但不一定是严格降序的，故对这些满足条件的再做一次排序即可。
• 

Solution_2:

 
ll a[1005],b[1005],c[1005];
 
int main() {
	int x,y,z,K; 
	cin >> x >> y >> z >> K;
	for(int i=0;i<x;i++) cin >> a[i];
	for(int i=0;i<y;i++) cin >> b[i];
	for(int i=0;i<z;i++) cin >> c[i];
	sort(a,a+x,greater<ll>());
	sort(b,b+y,greater<ll>());
	sort(c,c+z,greater<ll>());
	
	vector<ll> ans;
	for(int i=0;i<x;i++) {
		for(int j=0;j<y;j++) {
			for(int k=0;k<z;k++) {
                //按照序号依次取
				if((i+1)*(j+1)*(k+1) <= K) ans.push_back(a[i]+b[j]+c[k]);
			}
		}
	}
	sort(ans.begin(),ans.end(),greater<ll>());
	for(int i=0;i<K;i++) cout << ans[i] << endl;
	return 0;
}

Analysis_3: 

• 顺着上面的思路，（分别排好序后）和最大的肯定是 ，次大的一定是 三者其一，即只将一个最大值改为次大值，以此类推，每次都面临相同的选择，故我们要动态维护这个最大值，自然可以想到用优先队列（priority_queue）。当前的最大值如果是 ，则就把上述的三个值丢到这个大根堆里，进行 K 次操作即可。
• 此外，还需要考虑重复的情况，比如由  可以产生 ，而  也可以产生 ，故可用 map 对下标组合去重（而不是对和的值去重！！），具体细节注意一下可以用 pair套pair 来确定3个下标，当然也可以再开个结构体去重载小于号（懒得写有点麻烦....）
• 

Solution_3:

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
ll a[1005],b[1005],c[1005];
 
struct Node{
	int i,j,k;
	Node(){}
	Node(int i,int j,int k):i(i),j(j),k(k){}
	
	bool operator < (const Node &A) const {
		return a[i]+b[j]+c[k] < a[A.i]+b[A.j]+c[A.k];
	}
};
 
priority_queue<Node> pq;
map<pair<pair<int,int>,int>,int> mp; //下标组合去重
 
int main() {
	int x,y,z,K; 
	cin >> x >> y >> z >> K;
	for(int i=0;i<x;i++) cin >> a[i];
	for(int i=0;i<y;i++) cin >> b[i];
	for(int i=0;i<z;i++) cin >> c[i];
	sort(a,a+x,greater<ll>());
	sort(b,b+y,greater<ll>());
	sort(c,c+z,greater<ll>());
	
	pq.push(Node(0,0,0));
	mp[make_pair(make_pair(0,0),0)] = 1;
	while(K--) {
		Node now = pq.top();	
		int ni=now.i; int nj=now.j; int nk=now.k;
		pq.pop();
		cout << a[ni] + b[nj] + c[nk] << endl;
		// 下标合法 && 下标组合未重复
		if(ni+1 < x && !mp.count(make_pair(make_pair(ni+1,nj),nk))) {
			pq.push(Node(ni+1,nj,nk));
			mp[make_pair(make_pair(ni+1,nj),nk)] = 1;
		}
		if(nj+1 < y && !mp.count(make_pair(make_pair(ni,nj+1),nk))) {
			pq.push(Node(ni,nj+1,nk));
			mp[make_pair(make_pair(ni,nj+1),nk)] = 1;
		}
		if(nk+1 < z && !mp.count(make_pair(make_pair(ni,nj),nk+1))) {
			pq.push(Node(ni,nj,nk+1));
			mp[make_pair(make_pair(ni,nj),nk+1)] = 1;
		}
	}
	
	return 0;
}