Codeforces Round #433 (Div. 2) C. Planning（贪心）

一时失言乱红尘 2022-06-09 14:15 269阅读 0赞

C. Planning

time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are *n* flights that must depart today, the *i*\-th of them is planned to depart at the *i*\-th minute of the day.

Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first *k* minutes of the day, so now the new departure schedule must be created.

All *n* scheduled flights must now depart at different minutes between (*k* + 1)\-th and (*k* + *n*)\-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.

Helen knows that each minute of delay of the *i*\-th flight costs airport *c**i* burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

Input

The first line contains two integers *n* and *k* (1 ≤ *k* ≤ *n* ≤ 300 000), here *n* is the number of flights, and *k* is the number of minutes in the beginning of the day that the flights did not depart.

The second line contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 107), here *c**i* is the cost of delaying the *i*\-th flight for one minute.

Output

The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain *n* different integers *t*1, *t*2, ..., *t**n* (*k* + 1 ≤ *t**i* ≤ *k* + *n*), here *t**i* is the minute when the *i*\-th flight must depart. If there are several optimal schedules, print any of them.

Example

input

5 2
    4 2 1 10 2

output

20
    3 6 7 4 5

Note

Let us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles.

However, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20burles.

题解：

题意：

你很有可能赶不上飞机，你每拖延一分钟各种飞机要你交一定数额的拖延费，n为飞机数目，k为你要从第k秒开始赶飞机（当然只是单位时间，这里直接用秒了，一秒一辆真快），然后你可以任意选择登机顺序，使得你的拖延费最少，输入的是第i秒开始登机时每拖延一秒的费用，注意只能在登机开始后才能登机，不能提前登机

思路：

用一个优先队列，把可以登机的飞机加入套餐，由于这个费用每一秒增加是固定的，那么我们就选择每秒要交费用最多的那个，然后啪啪啪循环到底就行了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define eps 1e-7
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    struct node
    {
        int t;
        int v;
        friend bool operator<(node x,node y)
        {
            return x.v<y.v;
        }
    }a[300005];
    ll vis[300005];
    priority_queue<node>q;
    int main()
    {
        int i,j,n,k,d,ans=0,temp;
        ll s=0;
        node now;
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
        {
            vis[i]=0;
            scanf("%d",&a[i].v);
            a[i].t=i;
        }
        while(!q.empty())
            q.pop();
        d=min(n,k);
        d++;
        if(d<n)
            temp=d;
        else
            temp=n;
        for(i=1;i<=temp;i++)
        {
            q.push(a[i]);
        }
        for(i=1;i<=n;i++)
        {
            now=q.top();
            q.pop();
            vis[now.t]=d;
            s+=(ll)(d-now.t)*now.v;
            d++;
            if(temp<n)
            {
                q.push(a[temp+1]);
            }
            if(d<n)
                temp=d;
            else
                temp=n;
    
        }
        printf("%lld\n",s);
        printf("%lld",vis[1]);
        for(i=2;i<=n;i++)
            printf(" %lld",vis[i]);
        printf("\n");
        return 0;
    }