Lounge Lizards

题目链接

2017 United Kingdom and Ireland Programming Contest (UKIEPC 2017)

题解

中档题。题意大概是一群人(蜥蜴)看一个电视,如果电视与两个人在同一直线上且后面的人严格高于前面的才不会被挡住。问移除若干人(也可以不移除)后最多有多少人可以同时看电视且不会被挡住?
以电视为中心,对每个方向上的人的高度做LIS,之后将这些最长上升序列的元素个数相加即可。由于考虑到可能存在的精度问题,我并没有使用浮点数表示方向,而是使用x和y除去最大公约数后的值表示方向。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = (1 << 31) - 1;
const ll INF = 1ll << 60;

int tx, ty, n;
int q1;
struct Input {
    int x, y, flag, h;
}input[MAXN];
pair<int, pair<int, int>> temp;
set<pair<int, pair<int, int>>> pd;
map<pair<int, pair<int, int>>, vector<int>> nowh;

int dp[MAXN];

int lis(vector<int>&a){
    memset(dp, 0x3f, sizeof(int)*a.size());
    int len = 1;
    dp[0] = a[0];
    for (int i = 1; i < a.size(); ++i)    {
        int pos = lower_bound(dp, dp + len, a[i]) - dp;
        dp[pos] = a[i];
        len = max(len, pos + 1);
    }
    return len;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

pair<int, pair<int, int>> tran(Input a) {
    q1 = gcd(a.x, a.y);
    temp.first = a.flag;
    temp.second.first = a.x / q1;
    temp.second.second = a.y / q1;
    return temp;
}

inline bool eq(Input a, Input b) {
    return a.flag == b.flag&&a.h == b.h&&a.x == b.x&&a.y == b.y;
}

inline bool cmp(Input a, Input b) {
    return (a.flag == b.flag ? (a.x == b.x ? (a.y < b.y) : a.x < b.x) : a.flag < b.flag);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> tx >> ty >> n;
    for (int i = 1; i <= n; i++) {
        cin >> input[i].x >> input[i].y >> input[i].h;
        input[i].x -= tx;
        input[i].y -= ty;
        input[i].flag = (input[i].x > 0) * 233 + (input[i].y > 0);
        input[i].x = abs(input[i].x);
        input[i].y = abs(input[i].y);
    }
    sort(input + 1, input + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        tran(input[i]);
        nowh[temp].push_back(input[i].h);
    }
    int ans = 0;
    for (auto i : nowh) {
        ans += lis(i.second);
    }
    cout << ans << endl;
}

标签: geometry

添加新评论