1 条题解
-
0
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
- 702
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者