原題
?
題目大意
這道題的背景是農夫和牛爬山,給出山的高度L,農夫會從山底以rF的速度爬山,中途不會休息,牛會從山底以rB的速度爬山,可以在休息站休息并吃草,在第i個休息站休息ti時間,牛可以吃t*ci的草,第i個休息站的高度為xi.農夫和牛同時出發,要求牛在不被農夫追上的同時吃最多的草,輸出草的數量.數據保證rF大于rB,注意r的單位是s/m,每個休息站的高度嚴格遞增.
題目分析
這道題可以貪心解決,設一個len變量(記錄當前位置)和k變量(記錄當前牛在那個休息站),設一個ans(記錄草的數量),第一步先找出所有站中c最大的那個休息站,開頭牛直接沖到該站開始吃草,吃草的時間為 (x-len)*(v農夫-v牛),然后ans+=t*c.然后找剩下休息站中c最大的休息站,再循環一次上一步操作,直到牛在最后一個休息站吃完草就可以結束了,后面輸出ans即可.關于如何找c最大的休息站,可以事先用一個數組maxn[i]記錄第i個休息站往后的c值最大的休息站的下標,具體實現可以參考代碼.
?
代碼
?
1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <string> 8 #include <utility> 9 #include <queue> 10 #include <stack> 11 const int INF=0x3f3f3f3f; 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 cin>>l>>n>>r1>>r2; 21 for(int i=0;i<n;i++) 22 scanf("%d%d",&x[i],&c[i]); 23 //初始化數組maxn 24 int maxe=n-1; 25 maxn[n-1]=-1;//按照定義這個值是不存在的,因為n-1是最后一個休息站,設為-1方便結束循環 26 for(int i=n-2;i>=0;i--) 27 { 28 if(c[maxe]<c[i+1]) maxe=i+1; 29 maxn[i]=maxe; 30 } 31 32 int k=0,len=0; 33 long long ans=0; 34 35 //由于剛開始,按照定義k值是不存在的,因為牛剛開始并沒有在任何一個休息站里,所以要先處理一下第一步 36 if(c[maxe]<c[0]) maxe=0; 37 ans=(x[maxe]*r1-x[maxe]*r2)*c[maxe]; 38 len=x[maxe],k=maxe; 39 40 //循環直到牛在最后一個休息站吃完草結束 41 while(maxn[k]!=-1) 42 { 43 long long time=(x[maxn[k]]-len)*r1-(x[maxn[k]]-len)*r2; 44 ans=ans+c[maxn[k]]*time; 45 len=x[maxn[k]]; 46 k=maxn[k]; 47 } 48 cout<<ans<<endl; 49 return 0; 50 }
?
