Find the hotel HDU - 3193 （ST表RMQ）

Summer again! Flynn is ready for another tour around. Since the tour would take three or more days, it is important to find a hotel that meets for a reasonable price and gets as near as possible!

But there are so many of them! Flynn gets tired to look for any. It’s your time now! Given the <p i, d i> for a hotel h i, where p i stands for the price and d i is the distance from the destination of this tour, you are going to find those hotels, that either with a lower price or lower distance. Consider hotel h 1, if there is a hotel h i, with both lower price and lower distance, we would discard h1. To be more specific, you are going to find those hotels, where no other has both lower price and distance than it. And the comparison is strict.

Input

There are some cases. Process to the end of file.

Each case begin with N (1 <= N <= 10000), the number of the hotel.

The next N line gives the (p i, d i) for the i-th hotel.

The number will be non-negative and less than 10000.

Output

First, output the number of the hotel you find, and from the next line, print them like the input( two numbers in one line). You should order them ascending first by price and break the same price by distance.

Sample Input

3

15 10

10 15

8 9

Sample Output

1

8 9

题意：

给你n个酒店的信息，包括价格和距离，问有哪些酒店满足条件？

条件是：不存在任意一个其他的酒店价格和距离都比该酒店低。

思路：

我们先以价格为first标准对酒店进行排序，然后建立对去距离的ST表，

到第i酒店时询问比当前第i个价格低的酒店中最小的距离是多少？如果最小的距离小于第i个酒店的距离，那么该酒店就合法。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int *p);

const int maxn = 10010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

pii a[maxn];

int st1[maxn][25];//st表

void init(int n)

{

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

        st1[i][0] = a[i].se;

    }

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

        for (int j = 0; j + (1 << i) - 1 < n; j++) {

            st1[j][i] = min(st1[j][i - 1], st1[j + (1 << (i - 1))][i - 1]);

        }

    }

}

int query1(int l, int r)

{

    int k = (int)(log((double)(r - l + 1)) / log(2.0));

    return min(st1[l][k], st1[r - (1 << k) + 1][k]);

}

bool cmp(pii id1, pii id2)

{

    if (id1.fi != id2.fi) {

        return id1.fi < id2.fi;

    } else {

        return id1.se < id2.se;

    }

}

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    gbtb;

    int n;

    while (cin >> n) {

        repd(i, 0, n - 1) {

            cin >> a[i].fi >> a[i].se;

        }

        sort(a, a + n, cmp);

        init(n);

        std::vector<int> idset;

        int id = 1;

        rep(i, 0, n) {

            if (a[i].fi != a[id].fi) {

                id = i;

            }

            int num = query1(0, id - 1);

            if (num >= a[i].se) {

                idset.push_back(i);

            }

        }

        cout << sz(idset) << endl;

        for (auto x : idset) {

            cout << a[x].fi << " " << a[x].se << endl;

        }

    }

    return 0;

}

inline void getInt(int *p)

{

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    } else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

Find the hotel HDU - 3193 （ST表RMQ）

最新文章

热门文章