题目链接 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; } /* */转载于:https://www.cnblogs.com/Dup4/p/9433057.html
相关资源：离散化详解 例题 程序