25分求助,样例能过。
查看原帖
25分求助,样例能过。
195955
Kiritan楼主2021/9/8 19:19
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const double min(double a,double b){return a<b?a:b;}
int n;
double d1,d2,c,pr,ans;
class station{
    public:
        double s,pri;
};
class node{
    public:
        double s=0,pri=0;
        node* next;
};
node *head=new node,*tail=new node;
void createlink(double x,double y){
    node* p=new node;
    *p={x,y,nullptr};
    head->next==nullptr?head->next=p:tail->next=p;
    tail=p;
}
int main(int argc,char* argv[]){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>d1>>c>>d2>>pr>>n;
    station* sta=new station[n];
    *head={0,pr,nullptr};
    for(int i(0);i<n;i++)
        cin>>sta[i].s>>sta[i].pri;
    sort(sta,sta+n,[&sta](station a,station b)->bool{return a.s<b.s;});
    for(int i(0);i<n;i++)
        createlink(sta[i].s,sta[i].pri);
    node *p=new node,*tmp=new node;
    *tmp={d1,1000,nullptr};
    tail->next=tmp;tail=tmp;
    p=head;
    while(p->next!=nullptr){
        double minn=600;
        node* _p=new node;
        _p=p;
        while((_p->s-p->s)/d2<c&&_p->next!=nullptr){
            minn=min(minn,_p->pri);
            _p=_p->next;
        }
        if(_p==p){
            cout<<"No Solution";
            return 0;
        }
        double _pri=p->pri,_s=p->s;
        do{
            p=p->next;
        }while(p->pri!=minn&&p->next!=nullptr);
        ans+=(_pri*(p->s-_s)/d2);
    }
    cout<<fixed<<setprecision(2)<<ans;
    return 0;
}
2021/9/8 19:19
加载中...