# 72 条题解

• @ 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);
}
``````
• @ 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;
}

``````
• @ 2019-03-17 18:34:14

NICE

• @ 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;
}
``````
• @ 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;
}

``````
• @ 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
for i:=1 to n do
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.

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

二分答案（注意精度问题……）

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

• @ 2019-03-17 18:33:46

哈哈

• @ 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;
}
``````

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

• @ 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;
}

• @ 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';
}
*/你觉得哪个是正解？

• @ 2016-11-10 19:09:15
• @ 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; }```

• @ 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;
}

• @ 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，但是对于这样的题目是没有用武之地的。。。

• @ 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

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

• @ 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;
}
``````
• @ 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
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.
```

• @ 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);
}

• @ 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
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.

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

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

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

精度问题。。

ID
1450

7

2952

508

17%

11