思路:我们考虑由于没有人的区间会覆盖其他人,所以我们将区间按左端点排序,发现如果地盘长度已知,可以贪心地尽量往左放,来判断是否有解,因此做法很简单,就是二分答案,然后O(n)贪心判定,复杂度为O(nlogn)
满分程序:
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
const long double eps=1e-;
int n;
struct node{
long double l,r;
}a[];
bool cmp(node q,node w){
if (q.l==w.l) return q.r<w.r;
return q.l<w.l;
}
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool check(long double mid){
long double last=,len=;
for (int i=;i<=n;i++){
len=std::max(a[i].r-std::max(a[i].l,last),(long double)0.0);
if (len<mid) return ;
last=std::max(a[i].l,last)+mid;
}
return ;
}
ll gcd(ll a,ll b){
if (b==) return a;
else return gcd(b,a%b);
}
void getpq(long double x,ll &p,ll &q){
long double mod=1e8,tmp;
p=,q=;
for (int i=;i<=n;i++){
tmp=fabs(x*i-(ll)(x*i+.));
if (tmp<mod)
mod=tmp,q=i,p=(ll)(x*i+.);
}
ll t=gcd(p,q);
p/=t;
q/=t;
}
int main(){
int T=read();
while (T--){
n=read();
for (int i=;i<=n;i++)
a[i].l=read(),a[i].r=read();
std::sort(a+,a++n,cmp);
long double l=,r=1e8;
while (r-l>eps){
long double mid=(l+r)/;
if (check(mid)) l=mid;
else r=mid;
}
ll p,q;
getpq(l,p,q);
printf("%lld/%lld\n",p,q);
}
}
注意:
(1)没开longdouble,这个错误率好像比较小。。
(2)eps开的不够小,这很可能WA
(3)输出的时候,有没有和其他的方案比较一下,谁的误差比较小。
真是个惨痛的教训。。。T_T