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即可,由此剪了很多很多的时间复杂度