【洛谷】P2179 [NOI2012]骑行川藏-白红宇

【洛谷】P2179 [NOI2012]骑行川藏

阅读量：5277 次

发布时间：2019-06-14

本文共 1710 字，大约阅读时间需要 5 分钟。

题解

感谢小迪给我讲题啊，这题小迪写挺好的我就不写了吧

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            //#define ivorysi#define eps 1e-8#define mo 974711#define pb push_back#define mp make_pair#define pii pair
            
             #define fi first#define se second#define MAXN 10005#define space putchar(' ')#define enter putchar('\n')using namespace std;typedef long long int64;typedef unsigned int u32;typedef unsigned long long u64;typedef double db;const int64 MOD = 1000000007;template
             
              void read(T &res) { res = 0;char c = getchar();T f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f;}template
              
               void out(T x) { if(x < 0) putchar('-'); if(x >= 10) { out(x / 10); } putchar('0' + x % 10);}int N;db E,s[MAXN],k[MAXN],v[MAXN];db getv(db x,int id) { db l = max(0.0,v[id]),r = 100000; int cnt = 50; db t = -1 / x; while(cnt--) { db mid = (l + r) / 2; if(mid * mid * (mid - v[id]) * 2 * k[id] <= t) l = mid; else r = mid; } return l;}db calc(db x) { db res = 0; for(int i = 1 ; i <= N ; ++i) { db t = getv(x,i); res += k[i] * s[i] * (t - v[i]) * (t - v[i]); } return res;}void Solve() { scanf("%d%lf",&N,&E); for(int i = 1 ; i <= N ; ++i) { scanf("%lf%lf%lf",&s[i],&k[i],&v[i]); } int cnt = 100; db L = -100000,R = 0; while(cnt--) { db MID = (L + R) / 2; if(calc(MID) <= E) L = MID; else R = MID; } db ans = 0; for(int i = 1 ; i <= N ; ++i) { ans += s[i] / getv(L,i); } printf("%.6lf\n",ans);}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Solve(); return 0;}