E - Kth Takoyaki Set

E - Kth Takoyaki Set

题目来源：E - Kth Takoyaki Set (atcoder.jp)

题目大致意思：

给你几个数，把他们各种排列的和（每个数字可以多次使用，不一定每个数字都要选）的第k小的ans是多少

思路：

第一想法是背包吧，但是很明显这个作为val的范围第一很大，第二无法确定正确的范围，总之很难写

于是我就想了第二种方法，假设当前可能有n种答案作为当前答案,其中最小的为k，那么下一个答案肯定是已有答案中加上当前最小值k

于是就有了广搜的超时代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<long long>s;//我的第1想法是背包，放弃了，第二想法是广搜
priority_queue<int,vector<int>, greater<int> >q;
signed main(){
	ios::sync_with_stdio(false);
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		long long p;
		cin >> p;
		q.push(p);
	}
	while(!q.empty()&&s.size()<k){
		int v=q.top();
		q.pop();
		if(s.size()!=0&&v==s[s.size()-1]){
			continue;
		}
		s.push_back(v);
		if(s.size()==k){
			break;
		}
		for(int i=0;i<s.size();i++){
			if(s.size()>=k){
				break;
			}
			q.push(v+s[i]);
		}
	}
	cout<<s[k-1];
	
}

这个代码很容易理解，那么剪肢时间就来了

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<long long>s;//我的第1想法是背包，放弃了，第二想法是广搜
priority_queue<int,vector<int>, greater<int> >q;
long long val[15];
signed main(){
	ios::sync_with_stdio(false);
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		long long p;
		cin >> p;
		q.push(p);
		val[i]=p;
	}
	while(!q.empty()&&s.size()<k){
		int v=q.top();
		q.pop();
		if(s.size()!=0&&v==s[s.size()-1]){
			continue;
		}
		s.push_back(v);
		if(s.size()==k){
			break;
		}
//		for(int i=0;i<n;i++){//这里有问题，因为前几个不一定就是1-n 
////			q.push(v+s[i]);
//		}
		//改为 
		for(int i=1;i<=n;i++){
			q.push(v+val[i]);
		}
	}
	cout<<s[k-1];
	
}

思路就是，将原来最小值k加所有已经有的答案作为下一次答案改为了将最小值k加最先给你的那10个数作为下一次答案

为什么，可以想到，在所有已有的答案中，必然有一些是有重复选择的，比如说答案n可能是由a1+a1+a2组成的，而这个肯定比a1、a2大，我们只需要判断a1即可,由此剪了很多很多的时间复杂度