Codeforces contest 853 A Planning(优先队列贪心)

Description

分别在1~N分钟该起飞的航班，因技术问题全部推迟k分钟起飞，但现在可以重新安排k+1 ~ k+1+N这N分钟，每分钟起飞一个航班，前提是不能比起初计划早。每个航班每推迟一分钟有代价c[i]，求最小代价及安排。

Analyze

原想着：贪心给每个航班参考代价安排起飞时间，先安排代价大的航班，可是发现一个问题，不能保证最后剩余的时间合理(满足前提)，就是说假如最后剩余的航班原计划在第5分钟起飞但(由于我的分配策略)只剩下第3分钟了…

换位思考：既然给航班分配起飞时刻不行，不如给起飞时刻分配航班。

给当前时刻分配时间合理的、代价最大的航班，把时间合理的航班放进一个人容器里，从中找出代价最大的，用优先队列。

Code

#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
typedef pair<ll, ll> P;
const int N = 300005;

P fli[N];

int main()
{
    ll n, k;
    while(~scanf("%lld%lld", &n, &k))
    {
        ll ans = 0, first = 0, second;
        priority_queue<P, vector<P>, less<P> > q;
        vector<P> vec;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld", &first);
            fli[i] = P(first, i);
        }
        for(int i = 1; i <= k; ++i)
            q.push(fli[i]);
        for(int i = k + 1; i <= k + n; ++i)
        {
            if(i <= n)
                q.push(fli[i]);
            first = q.top().first;
            second = q.top().second;
            q.pop();
            ans += first * (i - second);
            vec.push_back(P(second, i));
        }
        cout << ans << '\n';
        sort(vec.begin(), vec.end());
        int sz = vec.size();
        for(int i = 0; i < sz; ++i)
            printf("%lld%c", vec[i].second, (i == sz - 1) ? '\n': ' ');
    }
    return 0;
}