1 条题解

  • 0
    @ 2024-12-22 11:04:03

    C++ :

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std ;
    
    struct Car {
        double cost ;
        bool cannot ;
        int left , right ;
        double V , has ;
    
        struct node {
            double v ;
            double money ;
    
            node( double v=0 , double money=0 ):v(v),money(money){}
            bool operator < ( const node a ) const {
                return money < a.money ;
            }
    
        }data[100000] ;
    
    
    
        Car( double V ):V(V){
            memset( data , 0 , sizeof( data ) ) ;
            cost = 0.0 ;
            cannot = false ;
            left = right = 0 ;
            has = 0.0 ;
        }
    
        void push( double t ) {
            if( cannot ) return ;
            node a(0,t) ;
            int p = lower_bound( data + left , data + right , a ) - data ;
            double c = 0.0 ;
            for( int i = p ; i < right ; i ++ ) c += data[i].v ;
            a.v = V - has + c ;
            data[p] = a ;
            right = p + 1 ;
            has = V ;
        }
    
        void use( double t ) {
            if( has < t || cannot ) {
                cannot = true ;
                return ;
            }
            has = has - t ;
            double c = 0.0 ;
            while( c + data[left].v < t ) {
                c += data[left].v ;
                cost += data[left].money*data[left].v ;
                left ++ ;
            }
            cost += data[left].money*(t-c) ;
            data[left].v -= t-c ;
        }
    
    };
    
    
    int main() {
    
        double S , V , D , P[10000] , dist[10000] ;
        int N ;
        scanf("%lf%lf%lf%lf%d" , &S , &V , &D , &P[0] , &N ) ;
        dist[0] = 0.0 ;
        for( int i = 1 ; i <= N ; i ++ ) {
            scanf("%lf%lf" , &dist[i] , &P[i] ) ;
        }
    
        Car ac( V ) ;
        ac.push( P[0] ) ;
        for( int i = 1 ; i <= N ; i ++ ) {
            ac.use( (dist[i]-dist[i-1])/D ) ;
            ac.push( P[i] ) ;
        }
        ac.use( (S-dist[N])/D ) ;
        if( ac.cannot ) printf("No Solution\n") ;
        else printf("%.2lf\n" , ac.cost ) ;
    
        return 0 ;
    }
    
    
    • 1

    信息

    ID
    289
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者