时间戳

首页 > 解决方案 > 解决虫洞 (ZCO 2012)

c++ - 解决虫洞 (ZCO 2012)

问题描述

描述：

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

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

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

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

例如，假设有 3 场比赛，(start,end) 时间分别为 (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 个空格分隔的整数 N、X 和 Y，其中 N 是比赛次数，X 是可以使用虫洞 V 的时间实例数，Y 是可以使用虫洞 W 的时间实例数. 接下来的 N 行描述了每场比赛。这 N 行中的每一行都包含两个空格分隔的整数 S 和 E，其中 S 是特定比赛的开始时间，E 是该比赛的结束时间，其中 S < E。下一行包含 X 个空格分隔的整数，它们是可以使用虫洞 V 的时间实例。下一行包含 Y 空间分隔的整数，它们是可以使用虫洞 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;
}

我尝试的是对下限和上限使用二进制搜索。并返回列表中最接近的整数。这应该导致最小的差异。这个代码 AC 在 90% 的测试用例中，但是两个测试用例的错误答案失败了。

标签： c++algorithmsortingbinary-search

解决方案

正确代码： 

#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;
}

推荐阅读