首页 > 代码库 > BZOJ 2697 特技飞行(贪心)

BZOJ 2697 特技飞行(贪心)

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2697

 

【题目大意】

  神犇航空开展了一项载客特技飞行业务。
  每次飞行长N个单位时间,每个单位时间可以进行一项特技动作,
  可选的动作有K种,每种动作有一个刺激程度Ci。
  如果连续进行相同的动作,乘客会感到厌倦,
  所以定义某次动作的价值为(距上次该动作的时间)*Ci,若为第一次进行该动作,价值为0。
  安排一种方案,使得总价值最大。

 

【题解】

  我们发现一个动作进行两遍收益才是最大的,进行第三遍的话,
  第二遍的位置完全是没有必要做动作的,
  所以我们将c按照大小排序,从最两段到中间放置从大到小的动作即可

 

【代码】

#include <cstdio>#include <algorithm>using namespace std;const int N=1010;int n,k,a[N];bool cmp(int a,int b){return a>b;}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=k;i++)scanf("%d",&a[i]);    sort(a+1,a+k+1,cmp);int l=1,r=n,ans=0;    for(int i=1;i<=k;i++){        ans+=(r-l)*a[i];        l++;r--;        if(l>=r)break;    }printf("%d\n",ans);    return 0;}

BZOJ 2697 特技飞行(贪心)