标签：index ch 处理 sum 问题 int cost 正数
正数通常比较好处理，那我们先想个办法把所有的负数转为正数，我们可以求一下所有负数的和 \(sum\) ，这一定是最小数，那我们考虑如何将其变小一点，无非是去掉一个加上的负数或是加上一个正数，诶，那这样，去掉负数不就等于加上一个正数吗，这样我们就可以将所有的负数转化为正数，选出来的数在加上 \(sum\) 即可。
那我们就开始考虑处理第 \(k\) 小的问题，数据太大，背包肯定不行，暴搜肯定会 \(T\) ,我们可以考虑一下暴搜的过程，唯一的问题就是无法使它先去优先遍历最优的答案，那我们考虑一种方式来维护最优，同样还能像暴搜一样依次去遍历状态，没错，优先队列就可以完成这些要求。
我们先按元素从大到小排序，用二元组 \(pair<cost,id>\) 表示一个方案，其中 \(cost\) 表示当前方案的花费, \(id\) 表示当前考虑到了第几个元素，我们维持一个 \(cost\) 的小根堆。
每当从堆中弹出一个方案 \((cost,index)\) , 因为它是当前最小的所以可以直接输出, 然后只需要将另外两个方案 \((cost+s[index+1],index+1)\),以及\((cost+s[index+1]-s[index],index+1)\)放入堆中即可.
这样的生成方式有一个好处, 生成的每个方案都是合法的而且生成的方案必然大于等于原方案, 因此可以用堆维护.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6+107;
int n,k;
int a[N],sum,s;
int f[N],num[N];
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > >q;
signed main()
{
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(a[i]>=0) break;
sum+=a[i];
a[i]=-a[i];
}
printf("%lld\n",sum);
k--;
sort(a+1,a+1+n);
q.push(make_pair(a[1],1));
while(!q.empty())
{
int x=q.top().first,y=q.top().second;
// cout<<x<<' '<<y<<endl;
q.pop();
printf("%lld\n",sum+x);
k--;
if(k==0) return 0;
if(y+1<=n) q.push(make_pair(x+a[y+1],y+1));
if(y+1<=n) q.push(make_pair(x+a[y+1]-a[y],y+1));
}
}
标签：index,
ch,
处理,
sum,
问题,
int,
cost,
正数
From： https://www.cnblogs.com/zhengchenxi/p/18428268