Codeforces 853A 贪心 优先队列

orz果然自己还是思维不太够，感觉这里的优先队列的存储有一些小技巧，T了无数次，终于决定还是看大佬的代码，大佬的代码莫名的短啊有木有。虽然看了好多次突然明白了23333

贪心的思想很容易可以看出来，问题就是怎么处理最优起飞的时刻出现冲突的情况了，最容易想到的是先按权值排序，外层循环n，每次选一个大于i且与i最接近的起飞时刻，

但是在选这个起飞时间的时候，最笨的办法就是从i开始向上循环，找一个最接近的未访问的时刻，然而……T了啊……必然T啊……略绝望，再怎么剪枝也没什么卵用……

下面来看一看大佬用优先队列的小技巧……

一开始的时候先把i<=k的入队，然后从i=k+1开始边入队边计算，怎么想到的……大概……多做题吧……

既然外层循环是n内层再加循环会T的话，那我们换一种循环的方式，把外层循环设为起飞时间【k+1,k+n】

因为我们每次取得起飞时间都是大于k的，先把i<=k的入队的话，那么我们在此后边入队边出队计算的时候起飞时间必然>=i，而且是大于等于i的最优解。

emmmmmm如果你也像我一样第一遍看不太懂的话，一定要那笔写一写，模拟一下过程，会发现……居然是这样吧……大概

感觉自己之前的想法跟正确的选取的循环的变量刚好相反……复杂度确是加了不少……积累吧……

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdio.h>
#include<iomanip>
#include<queue>
using namespace std;
int l,k,n;
struct fl
{
    int num, v;
    bool operator<(const fl a)const
    {
        return v < a.v;
    }
};
fl f[300005];
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;
        priority_queue<fl>q;
        for (int i = 1; i <= n; i++)
        {
            cin >> f[i].v;
            f[i].num = i ;
            //q.push(f[i]);
        }
        long long sum = 0;
        for (int i = 1; i <= k; i++)
        {
            q.push(f[i]);
        }
        for (int i = k+1; i <= k+n; i++)
        {
            if (i <= n)
                q.push(f[i]);
            fl a = q.top();
            q.pop();
            sum += (long long)(i - a.num)*a.v;
            f[a.num].num = i;
        }
        cout << sum << endl;
        for (int i = 1; i <= n ; i++)
            cout << f[i].num << " ";
    return 0;
}