题解

72 条题解

  • 4
    @ 2017-06-24 12:32:39

    数据是在windows下生成的,因为评测环境不同导致浮点数精度有变化,于是很多题解里的代码都过不去了,这里发一下AC代码,祝大家AC愉快w。

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef long double db;
    int n;
    int x[200001],y[200001],s[200001];
    bool check(db v){
        db now=0;
        for(int i=1;i<=n;i++){
            now+=s[i]/v;
            if (now>y[i])
                return false;
            now=max(now,(db)x[i]);
        }
        return true;
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",x+i,y+i,s+i);
        db low=0,high=2e8,mid;
        while(true){
            if ((high-low)<1e-6)
                break;
            mid=(low+high)/2;
            if (check(mid))
                high=mid;
            else low=mid;
        }
        printf("%.2Lf",low);
    }
    
  • 1
    @ 2019-02-10 18:05:10

    一定要注意输入输出

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    using namespace std;
    const int maxn = 200005;
    int n,s[maxn];
    pair<int,int> t[maxn];
    long double vmin=0,vmax=2e8;
    bool check(long double x){
        long double tsum=0;
        for(int i=1;i<=n;i++){
            tsum += s[i]/x;
            if(tsum>t[i].second) return false;
            if(tsum<t[i].first) tsum = t[i].first;
        }
        return true;
    }
    void half(long double a,long double b){
        long double x = (a+b)/2;
        if(b-a<1e-6){
            vmax = x;
            return;
        }
        if (check(x)) half(a,x);
        else half(x,b);
    }
    int main(){
        scanf("%d",&n);
        t[0] = make_pair(0,0); s[0] = 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&t[i].first,&t[i].second,&s[i]);
        }
        half(vmin,vmax);
        printf("%.2Lf",vmax);
        return 0;
    }
    
    
  • 1
    @ 2017-11-04 15:47:16

    忍不住都要骂人了,c++的同志们,一定要用long double!!我因为long double 被第九个点卡的欲哭无泪,令人崩溃!long double!!!

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #define db long double
    using namespace std;
    int n;
    int x[200005],y[200005],s[200005];
    bool check(db v)
    {
        db last=0;
        for (int i=1; i<=n; i++) {
            db t=s[i]/v;
            last+=t;
            if (last>y[i]) return false; 
            last=max(last,(db)x[i]);
        }
        return true;
    }
    int main()
    {
        scanf("%d",&n);
        db l=0,r=2e8,mid=0;
        for (int i=1; i<=n; i++) {
            scanf("%d%d%d",&x[i],&y[i],&s[i]);
        }
        while (true){
            if (r-l<1e-8) break;
            mid=(l+r)/2;
            if (check(mid)) r=mid;
            else l=mid;
        }
        printf("%.2Lf\n",l);
        return 0;
    }
    
  • 1
    @ 2017-07-16 19:54:55
    # include <cstdio>
    # include <cmath>
    # include <algorithm>
    # include <cstdlib>
    # include <cstring>
    using namespace std;
    # define N 200008
    # define ac 0.000001
    int n=0;
    long double x[N]={0},y[N]={0},s[N]={0}; 
    long double l=0.0,r=10000000000,ans;
    long double p=0;
    
    bool pd(double v)
    {
        for(int i=1;i<=n;i++)
        {
            p+=s[i]/v;
            if(p>y[i]) return 0;
            if(p<x[i]) p=x[i];
        }
        return 1;
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%llf%llf%llf",&x[i],&y[i],&s[i]);
        }
        while(r-l>=ac)
        {
            double m=(l+r)/2.0;
            p=0;
            bool b=pd(m);
            if(b)r=m-ac,ans=r;
            else
            {
                l=m+ac;
            }
        }
        printf("%.2llf",ans);
        return 0;
    }
    
    
  • 1
    @ 2013-10-07 17:55:11

    要求2位,二分小数一定得精确到小数点后4-5位
    var
    i,j,k,m,n:longint;
    bb:boolean;
    sx,a,b:extended;
    l,r,ans:int64;
    x,y,s:array[1..200000] of longint;
    function check(num:int64):boolean;
    var
    i,j,k:longint;
    v,time:extended;
    begin
    check:=true;
    v:=num/100000;
    time:=0;
    for i:=1 to n do
    begin
    time:=time+s[i]/v;
    if 0<x[i]-time then time:=x[i]
    else if time-y[i]>0 then exit(false);
    end;
    end;
    begin
    readln(n);
    for i:=1 to n do
    readln(x[i],y[i],s[i]);
    l:=0;
    r:=1000000000000;
    while true do
    begin
    ans:=(l+r) div 2;
    bb:=check(ans);
    if bb=false then
    l:=ans
    else r:=ans;

    if r-l<=1 then break;
    end;

    bb:=check(l);
    if bb=true then
    ans:=l
    else ans:=r;

    a:=ans/100000;
    writeln(a:0:2);
    end.

  • 1
    @ 2009-06-29 16:03:22

    二分答案(注意精度问题……)

    p.s. 如果我们没有计算机,那这题可不简单……

  • 0
    @ 2019-08-19 15:40:36

    这道题还算水的吧。下面是代码。

    #include<bits/stdc++.h>
    typedef long long ll;
    typedef long double lb;
    typedef double db;
    using namespace std;
    struct node{
        db x,y,c;
    }a[210000];
    ll n,i;
    db l,r=2147483647,mid;
    int check(db l){
        lb s=0;
        for(i=1;i<=n;i++){
            s+=a[i].c/l;
            if(s>a[i].y)
                return 0;
            if(s<a[i].x)
                s=a[i].x;
        }
        return 1;
    }
    int main(){
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].c);
        while(r-l>=1e-9){
            mid=(l+r)/2;
            if(check(mid))
                r=mid;
            else
                l=mid;
        }
        printf("%0.2lf",l);
        return 0;
    }
    

    这道题在洛谷上就是个绿题

  • 0
    @ 2017-07-16 21:04:46

    纯cin、cout版本
    #include <iostream>
    #include <iomanip>
    #define N 200010
    int x[N],y[N],s[N];
    using namespace std;
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>x[i]>>y[i]>>s[i];
    long double v1=0,v2=1e7+1,k;
    while(v2-v1>1e-9)
    {
    k=(v1+v2)/2;
    long double t=0;
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
    t+=s[i]/k;
    if(t>y[i]) {flag=false;break;}
    if(t<x[i]) {t=x[i]*1.0;}
    }
    if(flag){v2=k;}
    else {v1=k;}
    }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<k<<endl;
    return 0;
    }

  • 0
    @ 2017-07-16 19:19:56

    #include<iostream>
    #include<iomanip>
    using namespace std;

    const int N=200000+5;
    double a[N],b[N],c[N],ans=N;
    int n;

    double Max(double x,double y)
    {
    return x>y?x:y;
    }

    bool search(double cost)
    {
    double time=0;
    int pos=1;
    while(pos<=n)
    {
    time+=(c[pos]/cost);

    if(time>b[pos])
    return false;
    else
    time=Max(a[pos],time);
    pos++;
    }
    return true;
    }

    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i]>>c[i];

    double left=0.000001,right=10000000,mid;

    while(right-left>=0.00001)
    {
    mid=(left+right)/2;
    if(search(mid))
    {
    right=mid-0.00001;
    ans=mid;
    }

    else
    left=mid+0.00001;
    }

    cout<<fixed<<setprecision(2)<<ans<<'\n';
    return 0;
    }
    /*
    //1450
    #include<iostream>
    #include<cstdio>
    #include <iomanip>
    using namespace std;

    typedef long double db;
    int n;
    int x[200001],y[200001],s[200001];

    bool check(db v){
    db now=0;
    for(int i=1;i<=n;i++){
    now+=s[i]/v;
    if (now>y[i])
    return false;
    now=max(now,(db)x[i]);
    }
    return true;
    }
    int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>x[i]>>y[i]>>s[i];

    db low=0,high=2e8,mid;
    while(1)
    {
    if ((high-low)<1e-6)
    break;

    mid=(low+high)/2;

    if (check(mid))
    high=mid;
    else low=mid;
    }
    cout<<fixed<<setprecision(2)<<low<<'\n';
    }
    */你觉得哪个是正解?

  • 0
    @ 2016-09-28 12:32:04

    精度问题aaaaaaaaaaaaaaaaaaaaaaaaa
    c++
    #include<cstdio>
    double x[200002],y[200002],s[200002];
    int n;
    double p;
    bool pd(double v){
    for(int i=1;i<=n;i++){
    p+=s[i]/v;
    if(p>y[i])return 0;
    if(p<x[i])p=x[i];
    }
    return 1;
    }
    int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%lf%lf%lf",&x[i],&y[i],&s[i]);
    double l=0.0,r=10000000000,ans;
    while(r-l>0.00001){
    double m=(l+r)/2.0;
    p=0;
    bool b=pd(m);
    if(b)r=m-0.00001,ans=r;else
    l=m+0.00001;
    }
    printf("%.2f\n",ans);
    return 0;
    }

  • 0
    @ 2016-09-27 21:34:17

    调来调去发现精度为小数点后10位不够,
    开到 0.000000000000001 过了
    #include <cstdio>
    #include <algorithm>
    #define M 200010
    #define ACR 0.000000000000001

    int n;
    double l=0.0001,r=9899999,mid;
    double x[M],y[M],d[M];

    int check(double v){
    int flag=1;
    double now=0;
    for(int i=1;i<=n;i++){
    now+=d[i]/v;
    if(now-y[i]<ACR&&now-y[i]>-ACR);//万一相等
    else if(now>y[i]){
    flag=0;
    break;
    }
    now=std::max(now,x[i]);
    }
    return flag;
    }

    int main(){
    freopen("express.in","r",stdin);
    freopen("express.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%lf%lf%lf",&x[i],&y[i],&d[i]);
    while(r-l>ACR){
    mid=(r+l)/2;
    if(check(mid))
    r=mid-0.001;
    else
    l=mid+0.001;
    }
    printf("%.2lf",mid);
    return 0;
    }

  • 0
    @ 2016-08-14 20:54:14
    #include <cstdio>
    #include <iostream>
    using namespace std;
    int n;
    double a[200005],b[200005],c[200005],ans=99999999;
    double L=0.000001,R=10000000,mid;
    bool verify(double parameter){
        double time=0;
        for (int i=1;i<=n;i++){
            time+=(c[i]/parameter);
            if (time<b[i]) time=max(a[i],time);
                else return false;
        }
        return true;
    }
    int main(){
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        while(R-L>=0.00001){
            mid=(R+L)/2;
            if (verify(mid)) {
                R=mid-0.00001;
                ans=mid;
            }
            else L=mid+0.00001;
        }
        printf("%.2f",ans);
    }
    

    其实STL的algorithm里面有binary_search,但是对于这样的题目是没有用武之地的。。。

  • 0
    @ 2016-07-08 22:57:36

    二分答案,比较恶心的就是精度问题。。
    程序倒是很简单。。
    ~~~
    #include <cstdio>
    int n;
    double ans,x[200005],y[200005],s[200005];
    bool is_v(double v){
    double t=0;
    for(int i=1;i<=n;i++){
    t+=double(s[i])/v;
    if(t<x[i])t=x[i];
    if(t>y[i])return false;
    }
    return true;
    }
    void binary_search(double l,double r){
    if(l>r){double t=l;l=r;r=t;}
    double m=(l+r)/2;
    if((r-l)<0.00001){ans=m;return;}
    if(is_v(m)) binary_search(l,m);
    else binary_search(m,r);
    }
    int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf%lf",x+i,y+i,s+i);
    binary_search(0.000001,10000000);
    printf("%.2lf\n",ans);
    return 0;
    }

    • @ 2016-07-08 22:58:35

      还有就是这题里的整数和实数都分不清,看着有可能是实数的就都用实数吧。。

  • 0
    @ 2016-05-11 19:59:11
    #include <cstdio>
    using namespace std;
    const int N=200000+5;
    double a[N],b[N],c[N],ans=N;
    int n;
    double Max(double x,double y)
    {return x>y?x:y;}
    bool try_(double cost)
    {
        double time=0;
        int pos=1;
        while(pos<=n)
        {
             time+=(c[pos]/cost);
             if(time>b[pos]) return false;
             else time=Max(a[pos],time);
           pos++;
        }
        return true;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
        double left=0.000001,right=10000000,mid;
           while(right-left>=0.00001)
             {
                mid=(left+right)/2;
                if(try_(mid)) {right=mid-0.00001;ans=mid;}   
                else left=mid+0.00001;
             } 
         printf("%.2f",ans);
        return 0;
    }
    
  • 0
    @ 2016-04-04 12:32:18

    “仅包括一个**整数**,结果保留**两位小数**。”
    我天真地相信了,然后取了ceil,然后WA。。。
    还有上界要够大
    ```pascal
    uses math;
    const maxn=100000000;
    var n,i:longint;
    a:array[0..200001,1..3] of qword;
    lb,ub,mid:extended;

    function c(k:extended):boolean;
    var i:longint;t:extended;
    begin
    t:=0;
    for i:=1 to n do begin
    t:=t+(a[i,3]/k);
    if t>a[i,2] then exit(false);
    if t<a[i,1] then t:=a[i,1];
    end;
    c:=true;
    end;

    begin
    read(n);
    for i:=1 to n do read(a[i,1],a[i,2],a[i,3]);
    lb:=0;ub:=maxn;

    for i:=1 to 100 do begin
    mid:=(lb+ub)/2;
    if c(mid) then ub:=mid
    else lb:=mid;
    end;
    writeln(ub:9:2);
    end.
    ```

  • 0
    @ 2015-10-23 21:04:18

    不得不说作为一个Cpp党,我的内心是崩溃的…………在自己的win电脑上面输出各种乱码,最后交了一个Lf真的是带着试试看的心理来提交的……强烈BS这道语言歧视题…………

    测试数据 #0: Accepted, time = 0 ms, mem = 5200 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 5200 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 5196 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 5200 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 5200 KiB, score = 10
    测试数据 #5: Accepted, time = 171 ms, mem = 5196 KiB, score = 10
    测试数据 #6: Accepted, time = 281 ms, mem = 5200 KiB, score = 10
    测试数据 #7: Accepted, time = 343 ms, mem = 5208 KiB, score = 10
    测试数据 #8: Accepted, time = 343 ms, mem = 5196 KiB, score = 10
    测试数据 #9: Accepted, time = 343 ms, mem = 5196 KiB, score = 10

    #include <cstdio>

    const int fio = 0;
    struct arr {
    double x, y, dis;
    } a[200007];
    long double l, r, mid, t;
    bool flag;
    int n;

    void file_stream() {
    if (fio) {
    freopen("express.in", "r", stdin);
    freopen("express.out", "w", stdout);
    }
    }

    int main() {
    file_stream();
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
    scanf("%Lf", &a[i].x);
    scanf("%Lf", &a[i].y);
    scanf("%Lf", &a[i].dis);
    }
    l = 1.0; r = 2e8;
    while (r - l > 0.00001) {
    mid = (l + r) / 2;
    t = 0.0;
    flag = true;
    for (int i = 1; i < n; i++) {
    t = t + a[i].dis / mid;
    if (t > a[i].y) {
    flag = false;
    break;
    }
    if (t < a[i].x)
    t = a[i].x;
    }
    if (!flag) l = mid;
    else {
    t = t + a[n].dis / mid;
    if (t < a[n].y) r = mid;
    else if (t > a[n].y) l = mid;
    else if (t == a[n].y) {
    printf("%.2Lf\n", mid);
    return 0;
    }
    }
    }
    printf("%.2Lf\n", l);
    }

  • 0
    @ 2015-10-23 19:56:11

    测试数据 #0: Accepted, time = 0 ms, mem = 3120 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 3120 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 3120 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 3120 KiB, score = 10
    测试数据 #4: Accepted, time = 2 ms, mem = 3124 KiB, score = 10
    测试数据 #5: Accepted, time = 93 ms, mem = 3120 KiB, score = 10
    测试数据 #6: Accepted, time = 156 ms, mem = 3120 KiB, score = 10
    测试数据 #7: Accepted, time = 187 ms, mem = 3120 KiB, score = 10
    测试数据 #8: Accepted, time = 187 ms, mem = 3120 KiB, score = 10
    测试数据 #9: Accepted, time = 203 ms, mem = 3120 KiB, score = 10

    type arra=record
    x,y,dis:longint;
    end;
    const maxn=200000000000;
    var
    l,r,mid,t:extended;
    a:array[1..200000] of arra;
    flag:boolean;
    i,n:longint;

    begin
    readln(n);
    for i:= 1 to n do readln(a[i].x,a[i].y,a[i].dis);
    l:=1; r:=maxn;
    while (r-l)>0.001 do
    begin
    mid:=(l+r)/2;
    i:=1;
    t:=0;
    flag:=true;
    while i<n do
    begin
    t:=t+a[i].dis/mid;
    if t>a[i].y then begin
    flag:=false;
    break;
    end;
    if t<a[i].x then t:=a[i].x;
    inc(i);
    end;
    if not(flag) then l:=mid
    else begin
    t:=t +a[n].dis/mid;
    if t<a[n].y then r:=mid
    else if t>a[n].y then l:=mid
    else if t=a[n].y then begin
    writeln(mid:0:2);
    halt;
    end;
    end;
    end;
    writeln(l:0:2);
    end.

  • 0
    @ 2014-01-01 12:01:40

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2013-10-29 19:55:14

    精度问题。。

信息

ID
1450
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
2950
已通过
507
通过率
17%
被复制
10
上传者