<题目链接>
题目大意：
表示有n架飞机本需要在[1,n]时间内起飞,一分钟只能飞一架.但是现在[1,k]时间内并不能起飞,只能在[k+1,k+n]内起飞.ci序号为i的飞机起飞延误一分钟的costi.每个飞机起飞时间不能比原定时间早,请安排一个起飞顺序,求最小的cost和。
解题分析：
贪心策略证明：转载于>>>
设序号为i的飞机起飞时间为di,则cost=∑(di-i)*cj=∑di*cj-∑j*cj。显然后一项为常数,而{di-k}为[1,n]的一个排列, 所以只要使ci越大的i尽可能早起飞即可使得cost最小。
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
#define N int(3e5+10)
ll ans[N];
struct Node{
ll loc,val;
Node(ll a1,ll a2):loc(a1),val(a2){}
bool operator < (const Node & tmp)const{
return val<tmp.val;
}
};
int main(){
ios::sync_with_stdio(false);cin.tie();cout.tie();
priority_queue<Node>q;
int n,k;cin>>n>>k;
ll sum=;
for(ll i=;i<=n+k;i++){
if(i<=n){
ll cal;cin>>cal;
q.push(Node(i,cal));
}
if(i>k){
Node now=q.top();q.pop();
sum+=(i-now.loc)*now.val; //起飞时间早的飞机与多的花费优先相乘
ans[now.loc]=i;
}
}
cout<<sum<<endl;
for(int i=;i<=n;i++)
i==n?printf("%lld\n",ans[i]):printf("%lld ",ans[i]);
}
2019-02-01