ZOJ - 3953 Intervals 【贪心】

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3953

题意

给出N个区间，求去掉某些区间，使得剩下的区间中，任何的三个区间都不两两相交。

思路

将所有区间以左端点为键值从小到大排序

然后三个三个一组进行判断

如果这三个中有两两相交的那么就删去右端点最大的因为这个区间对答案的贡献最小

然后三个区间当中没有两两相交的，那么下一次进来的区间就替换掉右端点最小的。

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 5e4 + 5;

const int MOD = 1e9 + 7;

int ans[maxn];

int pos;

struct Node

{

    int id;

    int l, r;

    void read()

    {

        scanf("%d%d", &l, &r);

    }

}q[maxn];

Node v[5];

bool comp(Node x, Node y)

{

    return x.l < y.l;

}

bool comp2(Node x, Node y)

{

    return x.r < y.r;

}

bool comp3(Node x, Node y)

{

    return x.r > y.r;

}

void solve()

{

    sort(v, v + 3, comp);

    bool flag = ((v[1].l <= v[0].r) && (v[2].l <= v[0].r) && (v[2].l <= v[1].r));

    if (flag)

    {

        sort(v, v + 3, comp2);

        ans[pos++] = v[2].id;

    }

    else

        sort(v, v + 3, comp3);

}

int main()

{

    int t;

    scanf("%d", &t);

    while (t--)

    {

        int n;

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)

        {

            q[i].read();

            q[i].id = i;

        }

        sort(q + 1, q + 1 + n, comp);

        v[0] = q[1];

        v[1] = q[2];

        pos = 0;

        for (int i = 3; i <= n; i++)

        {

            v[2] = q[i];

            solve();

        }

        sort(ans, ans + pos);

        printf("%d\n", pos);

        for (int i = 0; i < pos; i++)

        {

            if (i)

                printf(" ");

            printf("%d", ans[i]);

        }

        printf("\n");

    }

}

巴特西

ZOJ - 3953 Intervals 【贪心】

最新文章

热门文章