首页 > 代码库 > 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 特技飞行（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。