（codeforces 853A）Planning 贪心

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₁, c₂, ..., c_n (1 ≤ c_i ≤ 10⁷), 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₁, t₂, ..., 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.

sample input

5 2
4 2 1 10 2

sample output

20
3 6 7 4 5

事实证明想对思路也要会写才行啊...想出来了大概思路是cost花费大的排前面,但没想到用优先队列,导致我在怎么处理飞机不能提前起飞这点上整了半天.结果发现一发优先队列很优雅的就写出来了...另外也算是学到了贪心的证明吧

设序号为i的飞机起飞时间为di,则cost=∑(di-i)*ci=∑di*ci-∑i*ci.
显然后一项为常数,而{di-k}为[1,n]的一个排列,
所以只要使ci越大的i尽可能早起飞即可使得cost最小.

最后要注意一点容易踩坑的,最后类型转换里(long long)(i-id)*cost; 不能写成(long long)((i-id)*cost); 因为把括号写在外面,实际上里面的cost很大,相乘后会超出int范围,一些有效数字已经被舍掉了,这时再转long long已经晚了...

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 #include <algorithm>

 #include <cstdio>

 #include <queue>

 #pragma warning ( disable : 4996 )

 #define PERMAX 2

 using namespace std;

 int Max( int x, int y ) { return x>y?x:y; }

 int Min( int x, int y ) { return x>y?y:x; }

 const int inf = 0x3f3f3f3f;

 const int vspot = 3e5 + ;

 const int espot = 1e5 + ;

 struct node {

     int id, cost;

     bool operator < ( const node &x ) const

         { return cost < x.cost; }    //cost大于x.cost时返回false，此时cost优先级更高

 }p[vspot];

 int N, K, tim[vspot];

 int main()

 {

     while( ~scanf("%d %d", &N, &K) )

     {

         priority_queue<node> Q;

         long long ans = ;

         for ( int i = ; i <= N; i++ )

             { scanf("%d", &p[i].cost); p[i].id = i; }

         for ( int i = ; i <= K; i++ )

             Q.push(p[i]);

         int id, cost;

         for ( int i = K+; i <= N+K; i++ )

         {

             if (i<=N)

                 Q.push(p[i]);

             id = (Q.top()).id; cost = (Q.top()).cost; Q.pop();

             tim[id] = i;

             ans += (long long)(i-id)*cost; //注意外面不能再加括号了

         }

         printf("%lld\n", ans);

         for( int i = ; i < N; i++ )

             printf( "%d ", tim[i] );

         printf( "%d\n", tim[N] );

     }

     return ;

 }

巴特西

（codeforces 853A）Planning 贪心

Input

Output

sample input

sample output

最新文章

热门文章