思路:我们考虑由于没有人的区间会覆盖其他人，所以我们将区间按左端点排序，发现如果地盘长度已知，可以贪心地尽量往左放，来判断是否有解，因此做法很简单，就是二分答案，然后O(n)贪心判定，复杂度为O(nlogn)
满分程序:
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #define ll long long 7 const long double eps=1e-12; 8 int n; 9 struct node{ 10 long double l,r; 11 }a[200005]; 12 bool cmp(node q,node w){ 13 if (q.l==w.l) return q.r<w.r; 14 return q.l<w.l; 15 } 16 int read(){ 17 char ch=getchar();int t=0,f=1; 18 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 19 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 20 return t*f; 21 } 22 bool check(long double mid){ 23 long double last=0,len=0; 24 for (int i=1;i<=n;i++){ 25 len=std::max(a[i].r-std::max(a[i].l,last),(long double)0.0); 26 if (len<mid) return 0; 27 last=std::max(a[i].l,last)+mid; 28 } 29 return 1; 30 } 31 ll gcd(ll a,ll b){ 32 if (b==0) return a; 33 else return gcd(b,a%b); 34 } 35 void getpq(long double x,ll &p,ll &q){ 36 long double mod=1e8,tmp; 37 p=0,q=0; 38 for (int i=1;i<=n;i++){ 39 tmp=fabs(x*i-(ll)(x*i+.5)); 40 if (tmp<mod) 41 mod=tmp,q=i,p=(ll)(x*i+.5); 42 } 43 ll t=gcd(p,q); 44 p/=t; 45 q/=t; 46 } 47 int main(){ 48 int T=read(); 49 while (T--){ 50 n=read(); 51 for (int i=1;i<=n;i++) 52 a[i].l=read(),a[i].r=read(); 53 std::sort(a+1,a+1+n,cmp); 54 long double l=0,r=1e8; 55 while (r-l>eps){ 56 long double mid=(l+r)/2; 57 if (check(mid)) l=mid; 58 else r=mid; 59 } 60 ll p,q; 61 getpq(l,p,q); 62 printf("%lld/%lld ",p,q); 63 } 64 }
注意:
(1)没开longdouble，这个错误率好像比较小。。
(2)eps开的不够小，这很可能WA
(3)输出的时候，有没有和其他的方案比较一下，谁的误差比较小。
真是个惨痛的教训。。。T_T