目录
题意
给定一个长度为n的序列A[]，你需要确定一个长度为n的排列P[]，定义当前排列的值为:
\[\sum_{i=1}^{n}{A[i]P[i]}\]
现在给定一个整数k,需要你求出，在所有可能的排列中(显然有n!种)，最小的k个"排列的值"是多少？依次输出。排列不同，值相同的，算不同的方案。
1<=n<=100000
输入格式
第一行为两个整数n,k,含义如题意所示。接下来n行为n个整数，代表A[]数组。
输出格式
输出k个整数，分别表示前k个"排列的值"，从小到大输出。
思路
感觉这道题比较神。
这里就不再提及骗分的做法了，直接说正解是怎样的。
首先第一步我都没想到...
可以将题目中的式子转化为：
\[\sum_{i=1}^{n}A_{P_i}(n-i+1)\]
不仅没想到，光是看懂这一步就花了我不少的时间。如果觉得比较显然的话，可以直接跳过下面的解说:
将问题转化之后，考虑如何从一个P[]转移到另外一个P'[]来得到连续的k个答案。但是在这之前，我们能够发现，在这种问题的定义下，初始状态下，A[]应该是递增的（因为要求值最小，所以说i=1是应乘一个较小的数）。
然后又是很神奇的一步：
考虑这样的一种转移:对于P[]数组而言，假设开始的t位都已经确定了（不能再改变），那么就考虑剩下的t+1~n个数字。
设一个位置u，一个长度v，保证u-v>t。当前我们令P[u-v]=P[u]，并将P[u-v~u-1]这一段区间内的数全部都向后移动一位,同时将t更新为u-v。也就是说整个数组由:P[u-v],P[u-v+1]...P[u]变为了P[u],P[u-v],P[u-v+1]...P[u-1]。
考虑这样变化之后，整个序列的值的增量是多少:P[u-v~u-1]都向右移了一段，而乘的数字是递减的(n,n-1,...3,2,1)，所以说减少了\(\sum_{i=u-v}^{u-1}A[P[i]]\)；又因为P[u]向左移了u-1-(u-v)+1=v格，所以增加了v*P[u]。将式子合并之后就成了\(\sum_{i=1}^{v}(A_{P_{u}}-A_{P_{u-i}})\)。设一次转移的增量是g(u,v)。由于我们已经发现了A[]是递增的，所以说g(u,v)>=g(u,v+1)，也就是说只有取v尽量小的时候是最优的。同样哦我们也能够发现，只有进行一次转移，值才有可能最小，所以说我们只需要考虑一次转移就可以了。
为啥这样子就能够代表所有可能状态的转移呢??下面又是博主的"想象":
然而一切才刚刚开始...
以上的分析只是一个前置而已...现在我们考虑一个解决这个问题的一个大致思路：通过对初始状态(A[]递增)进行上述的不断的变化，放进优先队列里面，每一次都把队首取出来，作为当前能够找到的最小的值输出，并在这个状态的基础上进行更新。在队列的每一个状态中，我们都需要维护一个可持久化的线段树，来维护区间内最小的g(u,v)以及u,v，还有当前这个区间内可用的A[]的个数s。
下面是一些实现细节：（）
- 开一个数组TMP[]来存一个状态。每一个位置存三个东西,一个叫Now的线段树表示当前这个状态还有那些状态能够使用，主要是为了方便查询下一步最优转移；一个叫Ori(Origin)的线段树，存这个状态最开始被放进队列的的时候长啥样，主要是为了求出下一步的转移后线段树应有的状态，而避免转移之间互相影响。还有一个数字sum，表示Ori对应的那个状态，也就是刚刚被放进队列的时候的序列的值。
- 最开始将A[]从小到大排序之后，将信息存储在TMP[0].Now里面，线段树的位置i表示A[i]-A[i-1]，即最小的转移。注意线段树中位置1一定要初始化为INF,因为A[0]是不存在的。
- 将TMP[0].Ori初始化为TMP[0].Now
- 将TMP[0]放进队列，注意插进去的答案为TMP[0].sum+TMP[0].Now->g，即转移一次之后的答案。
- 每一次将队列的头取出来(状态编号为T)，输出答案，然后进行更新:
- 更新的时候，其实就是将TMP[T].Ori进行了之前已经判断出来的一次转移之后的状态。申请新的状态num，表示上述含义。并将TMP[num].Now的初值赋为TMP[T].Ori，原因上上面已经说过了。然后将u-v-1之前的点全部删掉，因为t向后移了（忘记定义的往前找找）。再将原来的u删掉，因为它被移到u-v之后就在t上了，以后就固定了。再将原来的u-v那个地方的线段树中的值变为INF，因为它前面已经没有数字了。然后为原来的u+1寻找新搭配，因为它原来的搭配u已经被删除了。这样就完成了TMP[num].Now的更新。当然最后不忘将TMP[num].Ori赋为TMP[num].Now,然后再钦定转移后入队。
- 当然，如你所料，这还没完。因为要防止重复转移，但又要进行完所有可能的转移，这个时候就要发挥Now的作用了。这里将讲解如何将Now进行更新。首先，之后肯定是不可能再使用g(u,v)进行转移了，所以说我们要将这个状态转移去掉，将线段树中的u位置赋为新的转移方式g(u,v+1)。而根据之前增量公式可见，这个时候只需要加上A[P[u]]-A[P[u-v-1]]就可以了。然后..就没有然后了...最后记得将这个状态也钦点了转移之后入队。
可能博主说的有些含糊不清，，具体还请参见代码~~~
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 300000
#define INF 1000000000000000000LL
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
struct node
{
node *ch[2];
int u,v,s;
//u,v,g(u,v),s含义参上。u,v,s,都是再这个子区间的意义下的
LL g;
}tree[MAXN*40+5];
node *ncnt=&tree[0],*NIL=&tree[0];
struct ArrNode
{
node *Ori,*Now;
LL sum;
}TMP[MAXN*40+5];//状态节点
int tcnt=0;
LL A[MAXN+5];
int n,k;
priority_queue<PII,vector<PII>,greater<PII> > que;
void Init()
{
ncnt=NIL=&tree[0];
NIL->ch[0]=NIL->ch[1]=NIL;
NIL->u=NIL->v=NIL->s=0;
NIL->g=INF;
}
inline node* NewNode()
{
node *p=++ncnt;
p->ch[0]=p->ch[1]=NIL;
p->u=p->v=p->s=0;
p->g=INF;
return p;
}
void PushUp(node *rt)
{
node *lch=rt->ch[0],*rch=rt->ch[1];
if(lch->g<rch->g)
rt->g=lch->g,rt->u=lch->u,rt->v=lch->v;
else
rt->g=rch->g,rt->u=lch->s+rch->u,rt->v=rch->v;
rt->s=lch->s+rch->s;
}
void Build(node *&rt,int l,int r)
{
rt=NewNode();
rt->s=0;
if(l==r)
{
if(l>1) rt->u=rt->v=rt->s=1,rt->g=A[l]-A[l-1];
else rt->u=rt->v=rt->s=1,rt->g=INF;//注意特殊处理
return;
}
int mid=(l+r)/2;
Build(rt->ch[0],l,mid);
Build(rt->ch[1],mid+1,r);
PushUp(rt);
}
void Insert(node *&rt,int l,int r,int p,LL gval,int sval)
//Insert是+=，而change是直接赋值。而且Insert是找线段树的第p个，change是找第p个还存在的点
{
node *q=NewNode();
*q=*rt;rt=q;
if(l==r)
{
rt->g+=gval;
rt->u=rt->s=rt->v=sval;
return;
}
int mid=(l+r)/2;
if(p<=rt->ch[0]->s) Insert(rt->ch[0],l,mid,p,gval,sval);
else Insert(rt->ch[1],mid+1,r,p-rt->ch[0]->s,gval,sval);
PushUp(rt);
}
void ChangePoint(node *&rt,int l,int r,int p,LL gval,int sval)//与Insert的区别见上
{
node *q=NewNode();
*q=*rt;rt=q;
if(l==r)
{
rt->g=gval;
rt->u=rt->s=rt->v=sval;
return;
}
int mid=(l+r)/2;
if(p<=rt->ch[0]->s) ChangePoint(rt->ch[0],l,mid,p,gval,sval);
else ChangePoint(rt->ch[1],mid+1,r,p-rt->ch[0]->s,gval,sval);
PushUp(rt);
}
void DelSeg(node *&rt,int l,int r,int sum)
{
if(sum==0)
return;
int mid=(l+r)/2;
node *q=NewNode();
*q=*rt;rt=q;
if(rt->ch[0]->s>sum) DelSeg(rt->ch[0],l,mid,sum);
else DelSeg(rt->ch[1],mid+1,r,sum-rt->ch[0]->s),rt->ch[0]=NIL;
PushUp(rt);
}
LL Query(node *rt,int l,int r,int p)
{
if(l==r)
return A[l];
int mid=(l+r)/2;
if(rt->ch[0]->s>=p) return Query(rt->ch[0],l,mid,p);
else return Query(rt->ch[1],mid+1,r,p-rt->ch[0]->s);
}
void Extend(int T)
{
int Z=++tcnt;
node *&TN=TMP[T].Now,*&TO=TMP[T].Ori;
TMP[Z].sum=TMP[T].sum+TN->g;//先算值
TMP[Z].Now=TO;//下面再进行线段树形态的求解
int u=TN->u,v=TN->v,pos=u-v;//根据之前维护的信息求得当前的最优转移
//---------pos-pos+1-------u-----------
//---------pos+1--------u-pos----------
//先删掉u这个点
ChangePoint(TMP[Z].Now,1,n,u,INF,0);
//再删掉前面~pos-1的部分
if(pos-1>=1)
DelSeg(TMP[Z].Now,1,n,pos-1);
//为u+1重新寻找新的搭档
if(v+1<=TMP[Z].Now->s)
{
LL newval=Query(TMP[Z].Now,1,n,v+1)-Query(TMP[Z].Now,1,n,v);
ChangePoint(TMP[Z].Now,1,n,v+1,newval,1);
}
ChangePoint(TMP[Z].Now,1,n,1,INF,1);//原来的pos+1也已经失去了搭档了（因为此时为第一个可用的数）
//更新完成，保存初始状态
TMP[Z].Ori=TMP[Z].Now;
//对于TMP[Z]的更新完成了
que.push(PII(TMP[Z].sum+TMP[Z].Now->g,Z));
if(u-v-1>=1)
{
LL delta=Query(TN,1,n,u)-Query(TN,1,n,u-v-1);
Insert(TN,1,n,u,delta,1);//更新为g(u,v+1)
}
else
Insert(TN,1,n,u,INF,1);
que.push(PII(TMP[T].sum+TMP[T].Now->g,T));//钦定后入队
}
int main()
{
Init();
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&A[i]);
sort(A+1,A+1+n);
Build(TMP[0].Ori,1,n);//赋初值
for(int i=1;i<=n;i++)
TMP[0].sum+=A[i]*(n-i+1);//算最初的答案
TMP[0].Now=TMP[0].Ori;
printf("%lld\n",TMP[0].sum);//先把最小的值输出来
que.push(PII(TMP[0].sum+TMP[0].Now->g,0));//钦定转移并入队
for(int i=1;i<=k-1;i++)
{
PII fro=que.top();
que.pop();
printf("%lld\n",fro.first);//先输出早就钦定好的答案
Extend(fro.second);//再进行钦定后的结果的状态的更新
}
return 0;
}