题目链接
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;
}
/*
*/