我们先在set里放入a[0]~a[n-1]，此时最小值就是*S.begin()，然后我们将该最小值分别加上a[0]~a[n-1]，放入set，再删除S.begin()。
第二个最小值又是*S.begin()。
这为什么是对的呢？
假设某时刻答案为ans=a+b+c<*S.begin()，那么a+b一定没作为过最小值，因为那样一定会有a+b+c。
但是我们此时的*S.begin()>ans>a+b，所以a+b一定没出现在S中过，那么同理a一定没作为过最小值，但是a一开始就被放在了S中，且小于*S.begin()。
所以a一定作为过最小值，出现矛盾。
所以ans>=*S.begin()，显然ans>S.begin()不成立，所以*S.begin()==ans。
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=15; LL a[N]; int n,k; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; set<LL>S; S.insert(0); for(int i=1;i<=k;i++){ for(int j=0;j<n;j++)S.insert(*S.begin()+a[j]); S.erase(S.begin()); if(i==k)cout<<*S.begin()<<endl; } return 0; }
证明之利器：反证 + ><= 的语言来论证，讨论ans与自己策略得出的res的关系
当然贪心可以用玄学的策略更优来进行论证