AcWing 1517. 是否加满油
原题链接
中等
作者:
zysmmer
,
2021-02-05 21:14:46
,
所有人可见
,
阅读 435
无需复杂逻辑,简单粗暴10分钟秒掉
#include<iostream>
#include<algorithm>
using namespace std;
double DIS[50000];
typedef struct{
double price;
int distant;
}gas;
bool cmp(gas a,gas b){
return a.price>b.price;//价格大到小排序
}
int main(){
int CMAX,D,DAVG,N,k;
double sum=0;
cin>>CMAX>>D>>DAVG>>N;
gas G[510];
for(int i=0;i<N;i++){
cin>>G[i].price>>G[i].distant;
}
sort(G,G+N,cmp);
for(int i=0;i<N;i++){
for(int j=G[i].distant;j<G[i].distant+CMAX*DAVG;j++){
DIS[j]=G[i].price/DAVG;
}
}
for(k=0;k<D&&DIS[k];k++) sum+=DIS[k];
if(k==D) printf("%.2lf\n",sum);
else printf("The maximum travel distance = %d.00\n",k);
}
有点东西, 能到达的距离被较低价格更改,故最后为最低价格
大佬,这种贪心算法是怎么想到的啊?