[国家集训队]特技飞行

导言

在贪心题目中,排序算法总是和它一起出现,因此我们不难发现,有一类模型名为贪心+排序.

那么接下来,我们通过一道经典题目,感受一下这类模型的贪心为何和排序算法紧密不可分离.

题目描述

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

输入输出格式

输入格式:

第一行,两个数,N和K,如上所述;

第二行,K个正整数,表示K种动作的Ci值。

输出格式:

仅一行,一个整数,表示最大总价值。

输入输出样例

输入样例#1:

1
2
5 2
2 2

输出样例#1:

1
12

说明
对于10%的测试数据,$N \le 20$,$K \le 3$

对于全部的测试数据,$1 \le N \le 1000,1 \le K \le 300,0 \le Ci \le 1000$。


解题报告

题意理解

每一个时刻,你都可以安排一个项目,然后同一个项目,两次安排的时间间隔乘以它的刺激度,就是它的价值.现在请你做出一种安排,使得所有项目价值和最高.

每一个项目,可以安排次数不限.


思路确定

我们首先发现,一个项目其实当且仅当安排两次就好了.

  1. 少于两次,那么价值其实为0,还不如不安排.
  2. 大于两次,其实价值和两次的价值一样,如下图所示.

特技飞行.PNG


根据上图,我们就可以成功论证,一个项目只会出现两次.

综上所述,我们发现了,对于一个项目而言,间隔的距离最大,那么最后的价值就会最大.

间隔距离最大,那么显然就是最左端放一个,最右端放一个,那么此时显然距离最大.

但是间隔距离,会随着放的项目越来越多,而变得越来越短.

因此为了让最后的权值最大,我们不得不让,价值越高的项目,越在前面放置,使得他们的距离最大.


代码解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int n,m,k,a[N],ans;
int cmp(int a,int b)
{
return a>b;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=k;i++)
cin>>a[i];
sort(a+1,a+1+k,cmp);//贪心排序.
m=n-1;//最大距离
for(int i=1;i<=min(k,n/2);i++)
{
ans+=a[i]*m;//加上本次项目的价值
m-=2;//距离减少两个.因为放入了一对项目.
}
cout<<ans;
return 0;
}