解决虫洞 (ZCO 2012)

Question

描述：

今年是2102年，今天是ZCO的日子。今年有 N 场比赛，您知道每场比赛的开始和结束时间。您必须参加其中一场比赛。不同的比赛可能会重叠。不同比赛的时长可能不同

考试中心只有一个。有一个虫洞 V 可以把你从你家送到考试中心，另一个虫洞 W 可以把你从考试中心送回你家。显然，通过虫洞运输不需要任何时间；它是瞬时的。但是虫洞只能在特定的固定时间使用，这些你都知道。

所以，你用V虫洞到达考场，可能等下一次比赛开始前一段时间，参加比赛，可能再等一段时间再用W虫洞return 回家。如果你在时间 t1 通过 V 虫洞离开并在时间 t2 通过 W 虫洞返回，那么你花费的总时间是 (t2 - t1 + 1)。您的目标是花费尽可能少的总体时间，同时确保您参加其中一项比赛。

如果可能的话，您可以正好在比赛开始时间到达中心。如果可能的话，你可以在比赛结束的那一刻离开考场。你可以假设你总是能够参加至少一场比赛——也就是说，总会有一场比赛，前面有一个 V 虫洞，后面有一个 W 虫洞。

例如，假设有 3 场比赛，（开始，结束）时间分别为 (15,21)、(5,10) 和 (7,25)。假设V虫洞在4、14、25、2时间可用，W虫洞在13、21时间可用，那么你可以在14时间从V虫洞离开，从15时间开始参加比赛到21点，然后在21点使用W虫洞回家。因此你花费的时间是（21 - 14 + 1）= 8。你可以检查你不能做得比这更好。

输入：

第一行包含3个space分隔的整数N、X、Y，其中N为比赛次数，X为虫洞V可使用的次数，Y为次数可以使用虫洞 W 的时间实例。接下来的 N 行描述了每场比赛。这 N 行中的每一行包含两个 space 分隔的整数 S 和 E，其中 S 是特定比赛的开始时间，E 是该比赛的结束时间，S < E。下一行包含 X space 分隔的整数是可以使用虫洞 V 的时间实例。下一行包含 Y space 个分隔的整数，它们是可以使用虫洞 W 的时间实例。

输出：

打印包含单个整数的一行，即参加比赛所需花费的最短时间。

我的代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
#define loop(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define ll long long
#define inf 9223372036854775807
#define printgrid(arr,m,n){cout<<"[";for(int i=0;i<m;++i){if(i!=0)cout<<" ";cout<<"[";for(int j=0;j<n;++j){cout<<arr[i][j];if(j!=n-1)cout<<" ";}cout<<"]";if(i!=m-1)cout<<endl;}cout<<"]"<<endl;}
using namespace std;


int searchl(int *arr,int s,int v)
{
    int l=0;
    int r=s-1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if (arr[m] == v) return v;
        if(arr[m]<v)
        {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    if (r<0) r=0;
    return arr[r];
}

int searchh(int *arr,int s,int v)
{
    int l=0;
    int r=s-1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if (arr[m] == v) return v;
        if(arr[m]<v)
        {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    if(l>s-1) l=s-1;
    return arr[l];
}


int main() {
    int n,x,y;
    cin>>n>>x>>y;
    vector<pair<int,int>> v(n);
    int a[x];
    int b[y];
    loop(i,n) cin >> v[i].first >> v[i].second;
    loop(i,x) cin >> a[i];
    loop(i,y) cin >> b[i];
    sort(a,a+x);
    sort(b,b+y);

    int mn = 0x7fffffff;

    int l;
    int u;

    loop(i,n)
    {
        l = searchl(a,x,v[i].first);
        u = searchh(b,y,v[i].second);
        mn = min(mn,(u-l+1));
    }
    cout << mn << endl;
}

我尝试的是对下限和上限使用二进制搜索。和 return 列表中最接近的整数。这应该导致最低的差异。这段代码在 90% 的测试用例中都达到了 AC，但是有两个测试用例的答案是错误的。

Answer 1

正确代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
#define loop(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define ll long long
#define inf 9223372036854775807
#define printgrid(arr,m,n){cout<<"[";for(int i=0;i<m;++i){if(i!=0)cout<<" ";cout<<"[";for(int j=0;j<n;++j){cout<<arr[i][j];if(j!=n-1)cout<<" ";}cout<<"]";if(i!=m-1)cout<<endl;}cout<<"]"<<endl;}
using namespace std;


int searchl(int *arr,int s,int v)
{
    int l=0;
    int r=s-1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if (arr[m] == v) return v;
        if(arr[m]<v)
        {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    if (r<0) return -1;
    return arr[r];
}

int searchh(int *arr,int s,int v)
{
    int l=0;
    int r=s-1;
    while(l<=r)
    {
        int m = (l+r)/2;
        if (arr[m] == v) return v;
        if(arr[m]<v)
        {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    if(l>s-1) return -1;
    return arr[l];
}


int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    int n,x,y;
    cin>>n>>x>>y;
    vector<pair<int,int>> v(n);
    int a[x];
    int b[y];
    loop(i,n) cin >> v[i].first >> v[i].second;
    loop(i,x) cin >> a[i];
    loop(i,y) cin >> b[i];
    sort(a,a+x);
    sort(b,b+y);

    int mn = 0x7fffffff;

    int l;
    int u;

    loop(i,n)
    {
        l = searchl(a,x,v[i].first);
        u = searchh(b,y,v[i].second);
        if(u==-1 or l==-1) continue;
        mn = min(mn,(u-l+1));
    }
    cout << mn << endl;
}

解决虫洞 (ZCO 2012)

Solving Wormholes (ZCO 2012)

c++

sorting

algorithm

binary-search

描述：

输入：

输出：

我的代码：