空闲时间仍然做些题活动下脑筋，偶遇这题，感觉挺有意思的，难度不大，但真的实实在在的体现了贪心算法的核心价值观hhhh.......总的来说，就是在当下不断循环去寻找最近的最好的解，有好的解，就直接跳过去，没有的话就认为当下是最好的，然后往下走一步算一步~
题目链接
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main(int argc, char const *argv[])
{
double D1,C,D2,P;
int N;
cin>>D1>>C>>D2>>P>>N;
double* DD=new double[N+2];
double* PP=new double[N+2];
DD[0]=0;
PP[0]=P;
double max=C*D2;
for(int i=1;i<N+1;++i){
cin>>DD[i]>>PP[i];
}
for(int i=1;i<N+2;++i){
if(DD[i]-DD[i-1]>max){
cout<<"No Solution"<<endl;
return 0;
}
}
DD[N+1]=D1;
PP[N+1]=0;
int now=0;
double nowC=0;
double ret=0;
while(now<N+1){
int nearMinI=now;
double nearMin=PP[now];
for(int i=now+1;i<N+2;++i){
if(DD[i]-DD[now]>max){
break;
}
if(PP[i]<nearMin){
nearMin=PP[i];
nearMinI=i;
break;
}
}
if(nearMinI==now){
double needC=(D1-DD[now])/D2;
if(needC>C){
needC=C;
}
ret+=(needC-nowC)*PP[now];
nowC= needC- (DD[now+1]-DD[now])/D2;
++now;
}
else{
double needC=(DD[nearMinI]-DD[now])/D2;
if(needC>nowC){
ret+=(needC-nowC)*PP[now];
nowC=0;
}
else{
nowC-=needC;
}
now=nearMinI;
}
}
cout<<fixed<<setprecision(2)<<ret<<endl;
return 0;
}
