POJ - 2464 Brownie Points II 【树状数组 + 离散化】【好题】

题目链接

http://poj.org/problem?id=2464

题意

在一个二维坐标系上给出一些点

Stan 先画一条过一点的水平线

Odd 再画一条过Stan那条水平线上的任一点的垂直线

这两条线将坐标系分成了四个区域

Stan的得分为右上角区域的点数+左下角区域的点数

Ollie的得分为左上角区域的点数+右下角区域的点数

线上的点不归任何人所有

两人都采用最优策略使得自己的点数最大

最后输出 Stan的最大点数以及在Stan 这个最大点数的情况下，Ollie能够获得的最大点数

思路

首先可以想到，如果一个对应的x坐标那条垂直线上，只有一个点的话，那么对于那个点的情况，如果Stan选了那个点划线，那么Ollie 就没有选择

如果有多个点，Ollie 会选择使得自己分最高，或者有多个分最高的情况会选择Stan 分最低的划线

处理的话，，可以先对x排序，然后插入y 就是控制变量法，这样就可以得到一边的数量

比如第一次，按x从小到大过去，，可以得到左半边的数量

然后右半边只要从大到小再来一次合并一下答案就可以

然后没有给出x 和 y 的坐标范围，但是点数只有200000 ，只要离散化一下就可以

有一些坑点注意一下就可以

AC代码

#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cstring>

#include <cctype>

#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 <list>

#include <bitset>

#include <assert.h>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

//#include <xfunctional>   // greater less

//#include <unordered_map>

//#include <unordered_set>

using namespace std; 

namespace Dup4

{

    typedef long long ll;

    typedef long double ld;

    typedef long double ld;

    typedef unsigned long long ull;

    typedef pair <int, int> pii;

    typedef pair <ll, ll> pll;

    typedef pair <ll, int> pli;

    typedef vector <int> vi;

    typedef vector <ll> vll;

    typedef vector < vi > vvi;

    #define fi first

    #define se second

    #define pb push_back

    #define gc getchar

    #define pc putchar

    #define p32 pc(' ')

    #define p10 pc('\n')

    #define L(on) ((on)<<1)

    #define R(on) (L(on) | 1)

    //#define gcd(a,b) __gcd(a,b)

    #define lowbit(x) ((x)&(-x))

    #define mkp(a, b) make_pair(a, b)

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

    #define rall(x) x.rbegin(), x.rend()

    #define CLR(a, b) memset(a, (b), sizeof(a));

    #define random(a,b) ((a)+rand()%((b)-(a)+1))

    #define syn_close ios::sync_with_stdio(false); cin.tie(0);

    //__builtin_popcount(i) // 返回一个数中二进制形式中1的个数

    inline int read()

    {

        int x = 0, f = 1; char c = gc();

        for (; !isdigit(c); c = gc()) f ^= (c == '-');

        for (; isdigit(c); c = gc()) x = x * 10 + (c - '0');

        return x * (f ? 1 : -1);

    }

    template <typename T>

    inline void read(T &x)

    {

        x = 0; int f = 1; char c = gc();

        for (; !isdigit(c); c = gc()) f ^= (c == '-');

        for (; isdigit(c); c = gc()) x = x * 10 + (c - '0');

        x *= f ? 1 : -1;

    }

    template <typename T>

    inline void write(T x)

    {

        if (!x) { pc(48); return; }

        if (x < 0) x = -x, pc('-');

        int bit[20], i, p = 0;

        for (; x; x /= 10) bit[++p] = x % 10;

        for (i = p; i; --i) pc(bit[i] + 48);

    }

    //仅限于正整数读入

    inline char nc()

    {

        static char buf[100000], *i = buf, *j = buf;

        return i == j && (j = (i = buf) + fread(buf, 1, 100000, stdin), i == j) ? EOF : *i++;

    }

    template <typename T>

    inline void _read(T &sum)

    {

        char ch = nc(); sum = 0;

        while (!(ch >= '0' && ch <= '9')) ch = nc();

        while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();

    }

    template <typename T>

    inline T gcd(T a, T b)

    {

        while (b ^= a ^= b ^= a %= b);

        return a;

    }

    #ifdef LOCAL

        #define gets gets_s

        #define sp system("pause");

        #define bug puts("***bug***");

    #endif

    #ifdef ONLINE_JUDGE

        #define sp

        #define bug

    #endif

    const double PI = acos(-1.0);

    const double EI = exp(1.0);

    const double eps = 1e-8;

    const int INF = 0x3f3f3f3f;

    const ll INFLL = 0x3f3f3f3f3f3f3f3fll;

}

using namespace Dup4;

namespace FastIO

{

    // 只可读入 正整数，单字符

    #define BUF_SIZE 10000005

    bool IOerror = false;

    inline char NC()

    {

        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;

        if (p1 == pend)

        {

            p1 = buf;

            pend = buf + fread(buf, 1, BUF_SIZE, stdin);

            if (pend == p1)

            {

                IOerror = true;

                return -1;

            }

        }

        return *p1++;

    }

    inline bool blank(char ch)

    {

        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';

    }

    inline void __read(char &x)

    {

        char ch;

        while (blank(ch = NC()));

        if (IOerror)

        {

            x = -1;

            return;

        }

        x = ch;

    }

    template <typename T>

    inline void __read(T &x)

    {

        char ch;

        while (blank(ch = NC()));

        if (IOerror)

        {

            x = -1;

            return;

        }

        for (x = ch - '0'; isdigit(ch = NC()); x = x * 10 + ch - '0');

    }

    #undef BUF_SIZE

}

using namespace FastIO;

const int maxn = (int)2e5 + 10;

const int Maxn = (int)1e7 + 100;

const int MOD = (int)1e8 +7;

int n;

int y[maxn];

struct node

{

    int x, y;

    void scan()

    {

        x = read(), y = read();

    }

    bool operator < (const node& r) const

    {

        return x < r.x || x == r.x && y < r.y;

    }

}cor[maxn];

bool Input()

{

    if (n = read(), n == 0) return false;

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

        cor[i].scan(), y[i] = cor[i].y;

    sort(y + 1, y + 1 + n);

    int pos = unique(y + 1, y + 1 + n) - y - 1;

    //cout << pos << endl;

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

    {

        int it = lower_bound(y + 1, y + 1 + pos, cor[i].y) - y;

        cor[i].y = it;

        //printf("%d%c", cor[i].y, " \n"[i == n]);

    }

    return true;

}

int a[maxn];

void add(int x)

{

    for (int i = x; i < maxn; i += lowbit(i))

        a[i] ++;

}

int sum(int x)

{

    int ans = 0;

    for (int i = x; i > 0; i -= lowbit(i))

        ans += a[i];

    return ans;

}

int ans_Stan[maxn], ans_Ollie[maxn];

bool vis[maxn];

void Solve()

{

    CLR(a, 0); CLR(vis, false);

    sort(cor + 1, cor + 1 + n);

    int tot = 0; add(cor[1].y); ans_Stan[1] = 0; ans_Ollie[1] = 0;

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

    {

        if (cor[i].x == cor[i - 1].x)

            tot++;

        else

            tot = 0;

        add(cor[i].y);

        ans_Stan[i] = sum(cor[i].y - 1) - tot;

        ans_Ollie[i] = i - sum(cor[i].y);

    }

    tot = 0; CLR(a, 0); add(cor[n].y);

    for (int i = n - 1; i >= 1; i--)

    {

        if (cor[i].x == cor[i + 1].x)

            tot++;

        else

            tot = 0;

        ans_Stan[i] += (n - i) - sum(cor[i].y) - tot;

        ans_Ollie[i] += sum(cor[i].y - 1);

        add(cor[i].y);

    }

    int index = 1, MMax = 1, Max = 0;

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

    //  printf("%d %d %d %d\n", ans_Stan[i], ans_Ollie[i], cor[i].x, cor[i].y);

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

    {

        if (cor[i].x == cor[i - 1].x)

        {

            if (ans_Ollie[i] > ans_Ollie[MMax] || ans_Ollie[i] == ans_Ollie[MMax] && ans_Stan[i] < ans_Stan[MMax])

                MMax = i;

        }

        else

        {

            //printf("%d %d\n", i, MMax);

            for (int j = index; j < i; j++)

            {

                if (j == MMax)

                {

                    Max = max(Max, ans_Stan[j]);

                    continue;

                }

                //printf("%d %d\n", cor[j].x, cor[j].y - 100000);

                vis[j] = true;

            }

            index = i, MMax = i;

        }

        if (i == n)

        {

            for (int j = index; j <= n; j++)

            {

                if (j == MMax)

                {

                    Max = max(Max, ans_Stan[j]);

                    continue;

                }

                vis[j] = true;

            }

        }

    }

    //cout << Max << endl;

    vector <int> ans;

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

    {

        if (ans_Stan[i] == Max && vis[i] == false)

        {

            //printf("%d %d\n", cor[i].x, cor[i].y - 100000);

            ans.pb(ans_Ollie[i]);

        }

    }

    printf("Stan: %d; Ollie:", Max);

    sort(all(ans));

    for (int i = 0, len = ans.size(); i < len; i++)

        if (i == 0 || ans[i] != ans[i - 1])

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

    puts(";");

}

void Run()

{

    #ifdef LOCAL

        freopen("Test.in", "r", stdin);

        //freopen("1.out", "w+", stdout);

    #endif

        //t = read();

        while (Input())

            Solve(); 

    #ifdef LOCAL

        fclose(stdin);

        //fclose(stdout);

    #endif

}

int main()

{

    Run();

    return 0;

}

/*

*/

巴特西

POJ - 2464 Brownie Points II 【树状数组 + 离散化】【好题】

最新文章

热门文章