黄山家居网站建设怎么样,济南在线制作网站,个人网站可以放广告吗,萧山网站优化原题 题目大意 这道题的背景是农夫和牛爬山,给出山的高度L,农夫会从山底以rF的速度爬山,中途不会休息,牛会从山底以rB的速度爬山,可以在休息站休息并吃草,在第i个休息站休息ti时间,牛可以吃t*ci的草,第i个休息站的高度为xi.农夫和牛同时出发,要求牛在不被农夫追上的同时吃最多的…原题 题目大意 这道题的背景是农夫和牛爬山,给出山的高度L,农夫会从山底以rF的速度爬山,中途不会休息,牛会从山底以rB的速度爬山,可以在休息站休息并吃草,在第i个休息站休息ti时间,牛可以吃t*ci的草,第i个休息站的高度为xi.农夫和牛同时出发,要求牛在不被农夫追上的同时吃最多的草,输出草的数量.数据保证rF大于rB,注意r的单位是s/m,每个休息站的高度严格递增. 题目分析 这道题可以贪心解决,设一个len变量(记录当前位置)和k变量(记录当前牛在那个休息站),设一个ans(记录草的数量),第一步先找出所有站中c最大的那个休息站,开头牛直接冲到该站开始吃草,吃草的时间为 (x-len)*(v农夫-v牛),然后anst*c.然后找剩下休息站中c最大的休息站,再循环一次上一步操作,直到牛在最后一个休息站吃完草就可以结束了,后面输出ans即可.关于如何找c最大的休息站,可以事先用一个数组maxn[i]记录第i个休息站往后的c值最大的休息站的下标,具体实现可以参考代码. 代码 1 #include cstdio2 #include cmath3 #include iostream4 #include cstring5 #include algorithm6 #include vector7 #include string8 #include utility9 #include queue
10 #include stack
11 const int INF0x3f3f3f3f;
12 using namespace std;
13
14 long long c[100001],x[100001]; //开long long防止爆数据
15 int maxn[100001]; //maxn[i]的值是第i个休息站往后的c值最大的休息站的编号(不包括第i个休息站)
16
17 int main()
18 {
19 int l,n,r1,r2;
20 cinlnr1r2;
21 for(int i0;in;i)
22 scanf(%d%d,x[i],c[i]);
23 //初始化数组maxn
24 int maxen-1;
25 maxn[n-1]-1;//按照定义这个值是不存在的,因为n-1是最后一个休息站,设为-1方便结束循环
26 for(int in-2;i0;i--)
27 {
28 if(c[maxe]c[i1]) maxei1;
29 maxn[i]maxe;
30 }
31
32 int k0,len0;
33 long long ans0;
34
35 //由于刚开始,按照定义k值是不存在的,因为牛刚开始并没有在任何一个休息站里,所以要先处理一下第一步
36 if(c[maxe]c[0]) maxe0;
37 ans(x[maxe]*r1-x[maxe]*r2)*c[maxe];
38 lenx[maxe],kmaxe;
39
40 //循环直到牛在最后一个休息站吃完草结束
41 while(maxn[k]!-1)
42 {
43 long long time(x[maxn[k]]-len)*r1-(x[maxn[k]]-len)*r2;
44 ansansc[maxn[k]]*time;
45 lenx[maxn[k]];
46 kmaxn[k];
47 }
48 coutansendl;
49 return 0;
50 } 转载于:https://www.cnblogs.com/VBEL/p/10403166.html
