首页 > 代码库 > Codeforces 801C Voltage Keepsake 结构体sort排序+贪心
Codeforces 801C Voltage Keepsake 结构体sort排序+贪心
#include <bits/stdc++.h> using namespace std; struct In{ long long a, b; double t; }s[100005]; bool cmp(In p, In q) { if(p.t < q.t) return true; else if(p.t == q.t && p.a < q.a) return true; return false; } int main() { long long n, p; scanf("%lld%lld", &n, &p); long long sum1 = 0; for(long long i = 0; i < n; i++) { scanf("%lld%lld", &s[i].a, &s[i].b); sum1 += s[i].a; s[i].t = s[i].b * 1.0 / s[i].a; } if(sum1 <= p) { printf("-1\n"); } else { sort(s, s + n, cmp); //for(int i = 0; i < n; i++) // printf("%lld--a %lld--b %.9f--t\n\n", s[i].a, s[i].b, s[i].t); double time = s[0].t; double pow = s[0].t * p; double dis, x; long long sum = s[0].a; long long i = 1; while(i < n) { dis = s[i].t - time; if(sum > p) { x = pow / (sum - p); if(x <= dis) { printf("%.10f\n", time + x); break; } } pow = pow + dis * (p - sum); sum += s[i].a; time = s[i].t; i++; } if(i == n) { x = pow / (sum - p); printf("%.10f\n", time + x); } } return 0; }
Codeforces 801C Voltage Keepsake 结构体sort排序+贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。