83 条题解

  • 0
    @ 2009-10-29 11:22:38

    分多种情况考虑,仔细点就能过。

    Program p1253;

    var d,p,sum,f:array[0..100] of real;

    n,i,j:longint;

    s,c,dis,pri,k,min:real;

    begin

    readln(s,c,dis,pri,n);

    for i:=1 to n do

    readln(d[i],p[i]);

    d[0]:=0; d[n+1]:=s;

    p[0]:=pri; pri:=0;

    for i:=0 to n do

    sum[i]:=(d-d[i])/dis;

    f[0]:=sum[0]*p[0];

    k:=c-sum[0]; min:=p[0];

    for i:=1 to n do

    begin

    if sum[i]>c then begin writeln(-1); halt; end;

    if (p[i]k)and(p[i]>min)

    then begin

    f[i]:=f+k*min+(sum[i]-k)*p[i];

    k:=c-sum[i]+k;

    min:=p[i];

    end;

    if (sum[i]min)

    then begin

    f[i]:=f+sum[i]*min;

    k:=k-sum[i];

    end;

    end;

    writeln(f[n]:0:2);

    end.

  • 0
    @ 2009-11-01 17:59:56

    f[i]表示到第i个加油站所用的最小代价(假设终点为第n+1个加油站)。

    v[i]表示到第i个加油站时,箱内便宜油(比p[i]便宜)的最大体积。

    vv[i]表示v[i]的价值(费用)。

    则便宜油单价为vv[i]/v[i]。

    从i到j要使得费用最小的话:

    1>若p[j]>=p[i],应先用完箱内的便宜油,再尽量多的装入第i个加油站的油.(因为便宜,而且箱内的油不一定要用完,用的时候只需要付出vv[i]/v[i]的费用就行了)

    2>若p[j]若vv[i]/v[i]>=p[i],那么就用最小费用到达j,并使油箱为空。

    ii>若vv[i]/v[i]c*d2 then break else begin

    k:=(d[j]-d[i])/d2;

    if p[j]>=p[i] then begin

    v[j]:=c-k;

    if k>=v[i] then begin

    f[j]:=f[i]+vv[i]+(k-v[i])*p[i];

    vv[j]:=v[j]*p[i];

    end else begin

    f[j]:=f[i]+k*vv[i]/v[i];

    vv[j]:=(v[i]-k)*vv[i]/v[i]+(v[j]-v[i]+k)*p[i];

    end;

    end else begin

    if k>=v[i] then f[j]:=f[i]+vv[i]+(k-v[i])*p[i] else begin

    f[j]:=f[i]+k*vv[i]/v[i];

    if vv[i]/v[i]=maxf then writeln('-1') else writeln(f[n]-vv[n]:0:2);

    end.

  • 0
    @ 2009-09-23 09:09:28

    呃...cost每次都加成下一种油了...居然能80!!这个数据...那个弱啊

  • 0
    @ 2009-09-13 17:33:24

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    type

    re=record

    di,pi:real;

    end;

    var

    a:array [1..1000] of re;

    d1,d2,c,e,p,s,st,v,max,max1,s1:real;

    n,i,j,m,l,t,tt:longint;

    begin

    readln(d1,c,d2,p,n);

    for i:=1 to n do

    readln(a[i].di,a[i].pi);

    inc(n);

    a[n].di:=d1; a[n].pi:=999999;

    st:=c*d2;

    s:=0; s1:=0;

    v:=p;

    while s=d1 then

    a[n].pi:=v;

    for i:=t+1 to n do

    if (a[i].di

  • 0
    @ 2009-09-11 17:59:57

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    program ex;

    var i,j,n:longint;

    d,c,ans:real;

    dis,p:array[1..102]of real;

    procedure qsort(l,r:longint);

    var i,j:longint;

    mid,temp:real;

    begin

    i:=l;j:=r;

    mid:=dis[(l+r)div 2];

    repeat

    while dis[i]mid do dec(j);

    if ij;

    if i

  • 0
    @ 2009-08-28 23:52:38

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    var d1,c,d2,p0,w,sheng,cost,min:real;

    n,i,j,x,q:longint;

    d,p:array[0..1000]of real;

    begin

    readln(d1,c,d2,p0,n);

    for i:=1 to n do readln(d[i],p[i]);

    d[n+1]:=d1;

    p[0]:=p0;

    i:=0;

    sheng:=0;

    while i

  • 0
    @ 2009-08-27 13:13:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    var

    s,d1,c,d2,p1:real;

    k,i,j,n:longint;

    d,p:array[0..1000] of real;

    begin

    readln(d1,c,d2,p1,n);

    for i:=1 to n do readln(d[i],p[i]);

    d[0]:=0;p[0]:=p1;

    d[n+1]:=d1;p[n+1]:=0;

    for i:=1 to n+1 do

    if d[i]-d>c*d2 then begin writeln('-1');halt; end;

    i:=0;

    s:=0;

    while (ip[i]) do inc(j);

    if d[j]-d[i]c*d2) or (d[j]-d[k]>c*d2) do k:=k-1;

    s:=s+c*p[i]+((d[j]-d[i])/d2-c)*p[k];

    end;

    i:=j;

    end;

    writeln(s:0:2);

    end.

    水的。。。。。水的数据。。。。。

    明显有错误的代码,

    也ACACAC 。。。 烂死了。。。。。。。。

  • 0
    @ 2009-08-23 10:18:30

    郁闷 害我多提交一次 应该输出-1

    #include

    #include

    typedef struct node{

    float d;

    float j;

    float dist;

    }NODE;

    int main()

    {

    float money,maxoil,totald,speed,price;

    float tpdist,minj,tdist,maxdist;

    int m,i,j,k;

    NODE pnode[100];

    while(scanf("%f %f %f %f",&totald,&maxoil,&speed,&price)!=EOF)

    {

    scanf("%d",&m);

    for(i = 1; i 0.0;){

    for(j=k,minj=pnode[j].j; j pnode[j].j){

    k = j;

    minj = pnode[j].j;

    }

    }

    if(k == i){

    pnode[i].dist += tpdist;

    break;

    }

    for(j=k,tdist=0.0; j < i; j++)

    tdist += pnode[j].dist;

    if(maxdist-tdist > tpdist)

    pnode[k].dist += tpdist;

    else

    pnode[k].dist += (maxdist-tdist);

    tpdist = tpdist + tdist - maxdist;

    k++;

    }

    }

    for(money=0.0,i=0; i

  • 0
    @ 2009-08-16 10:49:42

    感觉程序有点 长,不过秒杀

    Program P1253;

    var d,p:array[0..1000] of extended;

    i,j,n,m:longint;

    ans,tot,d1,c,d2,k,rest:extended;

    q:boolean;

    procedure check;

    var i,j:longint;

    begin

    for i:=0 to n do

    if d-d[i]>c*d2 then begin writeln('-1'); halt; end;

    end;

    procedure ts;

    var i,j:longint;

    begin

    readln(d1,c,d2,p[0],n);

    d[n+1]:=d1; d[n+2]:=d1; p[n+1]:=100000; p[n+2]:=100000;

    d[0]:=0; ans:=0; rest:=0;

    for i:=1 to n do readln(d[i],p[i]);

    end;

    procedure main;

    var i,j:longint;

    begin

    check;

    i:=0;

    while ip[i]) and (j

  • 0
    @ 2009-08-11 21:04:50

    var

    d,p:array[0..100]of real;

    k,min1,min2,i,j,m,n:longint;

    d2,en,s,c,v:real;

    begin

    read(en,c,d2,p[0],n);

    d[n+1]:=en;

    for i:=1 to n do

    begin

    inc(j);

    read(d[j],p[j]); p[j]:=p[j];

    if d[j]=d[j-1] then

    begin

    if p[j]c*d2 then begin writeln('-1'); halt end;

    repeat

    min1:=0;min2:=0;

    j:=k;

    while (j

  • 0
    @ 2009-08-06 13:29:28

    为什么要改题?搞得我多提交了5次,我的AC率啊...

  • 0
    @ 2009-08-06 10:31:48

    少判断一种情况过了3组,

    晕了

  • 0
    @ 2009-08-03 16:24:57

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    数据较弱

    明显错误得过60

  • 0
    @ 2009-07-30 23:13:19

    呃。。每个地方的油价竟然一样。。

  • 0
    @ 2009-07-30 18:15:29
  • 0
    @ 2009-07-27 12:25:25

    题解(附程序):

  • 0
    @ 2009-07-18 13:02:23
  • 0
    @ 2009-07-17 15:49:24

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    ...看了题解之后第一次80,原来没有加油站的情况忘了。第二次才AC

  • 0
    @ 2009-07-14 18:34:30

    program lv;

    type

    t1=record

    price,cc:real;

    end;

    var

    line:array[1..150] of t1;

    i,j,k,m,n,tail,head:longint;

    price,ccc,min,charge,d,use,cost:real;

    c,dis,p:array[0..150] of real;

    begin

    readln(dis[0],ccc,d,p[0],n);

    dis[n+1]:=dis[0];

    dis[0]:=0;

    for i:=1 to n do

    readln(dis[i],p[i]);

    for i:=0 to n do begin

    c[i]:=(dis-dis[i])/d;

    if c[i]>ccc then begin

    writeln(-1);

    halt;

    end;

    end;

    tail:=1;

    head:=1;

    line[tail].price:=p[0]*2;

    line[tail].cc:=ccc;

    charge:=0;

    for i:=0 to n do begin

    head:=tail;

    while (head>=1) and (line[head].price>=p[i]) do begin

    charge:=charge+line[head].cc;

    dec(head);

    end;

    tail:=head+1;

    line[tail].cc:=charge;

    line[tail].price:=p[i];

    head:=1;

    use:=c[i];

    while (use>0)and (head=line[head].cc then begin

    use:=use-line[head].cc;

    cost:=cost+line[head].price*line[head].cc;

    inc(head);

    end

    else begin

    line[head].cc:=line[head].cc-use;

    cost:=cost+line[head].price*use;

    use:=0;

    end;

    end;

    for j:=head to tail do

    line[j-head+1]:=line[j];

    tail:=tail-head+1;

    charge:=c[i];

    end;

    writeln(cost:0:2);

    end.

  • 0
    @ 2009-06-27 01:44:40

    #include

    using namespace std;

    int main()

    {

    double c,ps,ds,le,ans=0.0,d[101],p[101];int ct,i,n,j;

    scanf("%lf%lf%lf%lf",&d[0],&c,&ps,&p[0]);scanf("%d",&n);

    for(i=1;i

信息

ID
1253
难度
6
分类
贪心 点击显示
标签
递交数
3363
已通过
807
通过率
24%
被复制
16
上传者