【习题 8-14 UVA - 1616】Caravan Robbers

在这里输入题意

【题解】

二分长度。
显然长度越长。就越不可能。
二分的时候。可以不用管精度。
直接指定一个二分次数的上限就好。
判断长度是否可行。直接用贪心就好。
->贪心(排序区间,尽量让新的区间右端点靠左一点。以便后面的区间有放的地方。

最后得到小数。

=>暴力枚举分母i是什么。

然后进行类似一个迭代!?的过程。

如果round(ans*i)/i和ans的差的绝对值更小。则更新分母、分子。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5;

int n;

pair<double,double> a[N+10];

bool ok(double len){

    double now = a[1].first + len;

    for (int i = 2;i <= n;i++){

        if (a[i].first<now){

            if (now+len>a[i].second) return false;

            now = now + len;

        }else{

            //a[i].first>=now

            if (a[i].first+len>a[i].second) return false;

            now = a[i].first+len;

        }

    }

    return true;

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    while (cin >> n){

        for (int i = 1;i <= n;i++) cin >> a[i].first>>a[i].second;

        sort(a+1,a+1+n);

        double l = 1,r = a[1].second-a[1].first,temp = -1;

        for (int i = 1;i <= 200;i++){

            double mid = (l+r)/2.0;

            if (ok(mid)){

                temp = mid;

                l = mid;

            }else r = mid;

        }

        ll pfenzi = 0,pfenmu = 1;

        for (int i = 1;i <= 100000;i++){

            ll fenzi = round(i*temp);

            if ( abs((double)fenzi/(1.0*i)-temp) <abs((double)pfenzi/(1.0*pfenmu) - temp)){

                pfenzi = fenzi;

                pfenmu = i;

            }

        }

        cout <<pfenzi<<"/"<<pfenmu<<endl;

    }

	return 0;

}

巴特西

【习题 8-14 UVA - 1616】Caravan Robbers

最新文章

热门文章