网站域名登,传奇网页版在线玩,找建设企业网站公司,wordpress 企业网站教程题目背景 1.wqs爱好模拟飞行。 2.clj开了一家神犇航空#xff0c;由于clj还要玩游戏#xff0c;所以公司的事务由你来打理。 注意#xff1a;题目中只是用了这样一个背景#xff0c;并不与真实/模拟飞行相符 题目描述 神犇航空开展了一项载客特技飞行业务。每次飞行长N个单…题目背景 1.wqs爱好模拟飞行。 2.clj开了一家神犇航空由于clj还要玩游戏所以公司的事务由你来打理。 注意题目中只是用了这样一个背景并不与真实/模拟飞行相符 题目描述 神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间每个单位时间可以进行一项特技动作可选的动作有K种每种动作有一个刺激程度Ci。如果连续进行相同的动作乘客会感到厌倦所以定义某次动作的价值为(距上次该动作的时间)*Ci若为第一次进行该动作价值为0。安排一种方案使得总价值最大。 输入输出格式 输入格式 第一行两个数N和K如上所述 第二行K个正整数表示K种动作的Ci值。 输出格式 仅一行一个整数表示最大总价值。 输入输出样例 输入样例#1 5 2
2 2 输出样例#1 12 说明 对于10%的测试数据N20K3 对于全部的测试数据1N10001K3000Ci1000。 /*这道题好像是集训队里面最水的一道题了没有之一
看大总价值最大不用想我的第一反应是要么贪心要么背包这是本人的条件反射
然后仔细一看唉原来是排序贪心下面来说一说这俩有啥用
排序顾名思义将无序变为有序那么在这里是用sort从小到大排为什么呢下面会讲
贪心怎么贪他题目中所述的要总价值最大那么在这里看来每个动作的价值是固定的所以只能改变极差因为动作不能连续相同所以从极差最大的开始不断缩小范围以至于左边界大于或等于右边界为止
贪完后就找一个变量ans来存总价值此时的ans是最大的价值*/
#includebits/stdc.h
using namespace std;
const int N 11000;
int n,k;
int c[N];
int l1,r,ans0;
int main()
{cinnk;for(int i1;ik;i)cinc[i];sort(c1,ck1);rn;for(int ik;i0;i--){ans(r-l)*c[i];r--;l;if(lr) break;}coutans;return 0;
} 转载于:https://www.cnblogs.com/xmex/p/10127657.html
