[國家集訓隊] 特技飛行

題目背景

1.wqs愛好模擬飛行。

2.clj開了一家神犇航空，由于clj還要玩游戲，所以公司的事務由你來打理。

注意：題目中只是用了這樣一個背景，并不與真實/模擬飛行相符

題目描述

神犇航空開展了一項載客特技飛行業務。每次飛行長N個單位時間，每個單位時間可以進行一項特技動作，可選的動作有K種，每種動作有一個刺激程度Ci。如果連續進行相同的動作，乘客會感到厭倦，所以定義某次動作的價值為(距上次該動作的時間)*Ci，若為第一次進行該動作，價值為0。安排一種方案，使得總價值最大。

輸入輸出格式

輸入格式：

第一行，兩個數，N和K，如上所述；

第二行，K個正整數，表示K種動作的Ci值。

輸出格式：

僅一行，一個整數，表示最大總價值。

輸入輸出樣例

輸入樣例#1：

5 2
2 2

輸出樣例#1：

12

說明

對于10%的測試數據，N<=20，K<=3

對于全部的測試數據，1<=N<=1000，1<=K<=300，0<=Ci<=1000。

/*這道題好像是，集訓隊里面最水的一道題了沒有之一
看大總價值最大，不用想我的第一反應是：要么貪心，要么背包（這是本人的條件反射）
然后仔細一看，唉！原來是排序+貪心，下面來說一說這倆有啥用
排序：顧名思義將無序變為有序，那么在這里是用sort，從小到大排（為什么呢？下面會講）
貪心：怎么貪？他題目中所述的要總價值最大，那么在這里看來，每個動作的價值是固定的所以只能改變極差，因為動作不能連續相同，所以，從極差最大的開始，不斷縮小范圍以至于左邊界大于或等于右邊界為止
貪完后就找一個變量ans來存總價值，此時的ans是最大的價值*/
#include<bits/stdc++.h>
using namespace std;
const int N = 11000;
int n,k;
int c[N];
int l=1,r,ans=0;
int main()
{cin>>n>>k;for(int i=1;i<=k;i++)cin>>c[i];sort(c+1,c+k+1);r=n;for(int i=k;i>0;i--){ans+=(r-l)*c[i];r--;l++;if(l>=r) break;}cout<<ans;return 0;
}

?