「NOIP2017模拟赛07.31」倒水

  题目链接：http://hhhoj.ngrok.cc/problem/7

  挺有意思的一道题，反正我第一反应二分

  无所畏惧.jpg

  非常显而易见的，要中和就要有温度差，且Tmin和Tmax中和后的温度为(Tmin,Tmax)

  那么只有以下3种情况有解：

  1、大水缸的T>Tmax

  2、大水缸的T<Tmin

  3、所有温度相等，此时答案为0，而且不需要特判，只要在判定前两种情况是大于小于号带上等号处理就好了

  对于第1种情况，可知最后的温度范围是[Tmax,T)，Tmax是满足条件的温度边界，所以可以二分(然而并不需要)，在判断确定Tmax合法后整体加数

  对于第2种情况更容易些，因为最后温度范围是(T,Tmin]，显然Tmin是满足条件的温度边界同时也是最大值，所以要么无解，要么Tmin就是答案

  Ps#好久没写Pascal了，还真的是有些怀念啊啊= =

  贴代码

var c,t:array[0..100005]of double;
     id:array[0..100005]of longint;
     maxT,maxC:double;
     bo,n:longint;
     ans,L,R,mid:double;
 procedure swap(var x,y:double);
  var t:double;
   begin
    t:=x;x:=y;y:=t;
   end;
 procedure qsort(L,R:longint);
  var i,j:longint;
      mid:double;
   begin
    i:=L;j:=R;mid:=t[random(R-L+1)+L];
    repeat
     while t[i]<mid do inc(i);
     while t[j]>mid do dec(j);
      if i<=j then begin
                    swap(t[i],t[j]);swap(c[i],c[j]);
                    inc(i);dec(j);
                   end;
    until i>j;
    if i<R then qsort(i,R);
    if L<j then qsort(L,j);
   end;
 procedure init;
  var i,j:longint;
   begin
 //   assign(input,'1.in');reset(input);
 //   assign(output,'1.out');rewrite(output);
    read(n);
    read(maxT,maxC);
    for i:=1 to n do read(t[i],c[i]);
   end;
 function check(var x:double):boolean;
  var i,j:longint;
      sum:double;
   begin
    sum:=0;
    for i:=1 to n do
     begin
      if maxT=t[i] then begin
                         if maxT<>x then exit(false);
                         continue;
                        end;
      sum:=sum+(t[i]*c[i]-c[i]*x)/(x-maxT);
      if sum>maxC then exit(false);
     end;
    if maxC>=sum then exit(true);
    exit(false);
   end;
 procedure main;
  var i,j:longint;
      dt:double;
   begin
    bo:=0;ans:=0;dt:=1e-6;
    qsort(1,n);
    if (maxT<=t[1]) then begin
                          if check(t[1]) then begin ans:=t[1];bo:=1;end;
                          exit;
                         end;
    if (maxT>=t[n]) then begin
                           if not check(t[n]) then exit; end;
                           L:=t[n];R:=maxT;
                           while R-L>=dt do
                             begin
                              mid:=(L+R)/2;
                              if check(mid) then begin
                                                  bo:=1;
                                                  ans:=mid;
                                                  L:=mid+dt;
                                                 end
                                            else R:=mid-dt;
                             end;
   end;
 procedure print;
   begin
    if bo=0 then writeln('Impossible')
            else begin
                  writeln('Possible');
                  writeln(ans:0:4);
                 end;
  // close(input);close(output);
   end;
 begin
  init;
  main;
  print;
 end.

【写的有漏洞的，欢迎路过大神吐槽】

  2017/07/31 23:01:39

  Ending.