题目链接:uva 10869 - Brownie Points II
题目大意:给定若干点,第一个人选中一个存在点的横坐标,第二个人选中该横坐标上的一点,以该点作原点建立坐标系,一、三象限的点属于第一个人,二、四象限属于第二个人,坐标轴上的不属于任何人。问说在第一个人获得点最多的情况下第二个人可能获得多少点。
解题思路:将所有点按照x坐标从小到大,y坐标从大到小排序,这样从左向右可以处理处每个点右上角的点的个数(用树状数组维护即可),然后从右向左处理即可得到左下角区域的点数。
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn = 200000;
set<int> vec;
int ans;
int N, R, C, fenx[maxn+5], rec[maxn+5];
int cntx[maxn+5], cnty[maxn+5], have[maxn+5];
struct point {
int x, y;
int rx, ry;
}p[maxn+5];
inline bool sort_y (const point& a, const point& b) {
return a.y < b.y;
}
inline bool sort_xby (const point& a, const point& b) {
if (a.x != b.x)
return a.x < b.x;
return a.y > b.y;
}
inline bool sort_xsy (const point& a, const point& b) {
if (a.x != b.x)
return a.x > b.x;
return a.y < b.y;
}
void add_treeArr (int x, int val) {
while (x <= maxn) {
fenx[x] += val;
x += lowbit(x);
}
}
int query_treeArr (int x) {
int ret = 0;
while (x) {
ret += fenx[x];
x -= lowbit(x);
}
return ret;
}
void init () {
memset(cntx, 0, sizeof(cntx));
memset(cnty, 0, sizeof(cnty));
memset(fenx, 0, sizeof(fenx));
for (int i = 0; i < N; i++)
scanf("%d%d", &p[i].x, &p[i].y);
sort(p, p + N, sort_y);
C = p[0].ry = 1;
add_treeArr(C, 1);
for (int i = 1; i < N; i++) {
if (p[i].y != p[i-1].y)
C++;
p[i].ry = C;
add_treeArr(C, 1);
}
sort(p, p + N, sort_xby);
R = p[0].rx = 0;
for (int i = 1; i < N; i++) {
if (p[i].x != p[i-1].x)
R++;
p[i].rx = R;
}
}
void set_ans (int ret, set<int> v) {
if (ret > ans) {
ans = ret;
vec.clear();
}
if (ret == ans) {
for (set<int>::iterator i = v.begin(); i != v.end(); i++)
vec.insert(N - ret - cntx[p[*i].rx] - cnty[p[*i].ry] + 1);
}
}
void solve () {
memcpy(rec, fenx, sizeof(fenx));
for (int i = 0; i < N; i++) {
have[i] = query_treeArr(C) - query_treeArr(p[i].ry);
add_treeArr(p[i].ry, -1);
cntx[p[i].rx]++;
cnty[p[i].ry]++;
}
ans = 0;
vec.clear();
memcpy(fenx, rec, sizeof(rec));
int pre = p[N-1].rx, ret = N;
set<int> oll;
for (int i = N-1; i >= 0; i--) {
int tmp = have[i] + query_treeArr(p[i].ry - 1);
add_treeArr(p[i].ry, -1);
if (p[i].rx != pre) {
set_ans(ret, oll);
pre = p[i].rx;
ret = N;
oll.clear();
}
if (ret > tmp) {
ret = tmp;
oll.clear();
}
if (ret == tmp)
oll.insert(i);
}
set_ans(ret, oll);
printf("Stan: %d; Ollie:", ans);
for (set<int>::iterator i = vec.begin(); i != vec.end(); i++)
printf(" %d", *i);
printf(";\n");
}
int main () {
while (scanf("%d", &N) == 1 && N) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
资源分类:Python库 所属语言:Python 资源全名:eth-brownie-1.7.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Flex的主题,加演示源码。。。黑色为主体色,超炫!
Brownie是M5StickV的离线对象检测应用,它会以可爱的声音告诉您对象的名称
资源分类:Python库 所属语言:Python 资源全名:eth-brownie-1.8.7.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源分类:Python库 所属语言:Python 资源全名:eth-brownie-1.9.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
如果您使用安装了Brownie,则需要将Brownie brownie-token-tester添加到同一虚拟环境中: pipx inject eth-brownie brownie-token-tester 通过pip 您可以通过安装最新版本: pip install brownie-token-tester ...
Conhecendo o Git安装→官方网站: ://git-scm.com/ →安装: ://git-scm.com/downloadsJogo para treinarramificaçãodo Git Git possui uma arquitetura发行,这是具有重大意义的,也可以从tebalá的pro prototo...
资源分类:Python库 所属语言:Python 使用前提:需要解压 资源全名:eth_brownie-1.11.10-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
要与本地环境中的已部署合同进行交互,请先打开控制台: brownie console 接下来,部署测试令牌: >> > token = Token . deploy ( "Test Token" , "TST" , 18 , 1e21 , { 'from' : accounts [ 0 ]})Transaction ...
自述文件 环境变量 合同所有者地址export PRIVATE_...eth-brownie`pip3 install eth-brownie' 编制合同 输入目录cd CrowdCoin 编译brownie compile -all 部署合同 在ganache brownie run scripts/deploy.py --network
资源分类:Python库 所属语言:Python 资源全名:eth_brownie-1.3.2-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源来自pypi官网。 资源全名:Brownie-0.3.1.tar.gz
可以与密码验证机制集成易于使用:简单的GUI可以轻松控制和配置外壳永久:将数据存储在RxDB存储中(由PouchDB支持) 通过一个应用程序控制多个外壳:跟踪所需的多个外壳,并在它们之间无缝切换请注意,BROWNIE TUB...
scale_selector: :bookmark_tabs:设置cp .env.sample to .env然后用端点填充.env发展$ yarn dev在主网fork上测试要求: python3 (to install pipx)python3-pip (to install pipx)python3-venv (to install brownie)...
布朗尼图书馆是互补概念的集合。 重点在于独立于具体操作系统和编程语言的新概念的开发,并为不同的目标提供广泛的端口。
pip install eth-brownie 克隆此仓库 git clone https://github.com/PatrickAlphaC/nft-mix cd nft-mix 和 npm install -g ganache-cli npm install @openzeppelin/contracts 如果您希望能够部署到测试网,请执行...
Brownie-Lovers:Parcial 1 Pagina布朗尼情人
链环虹膜 用例 区块链交易事件的自动化文本,语音和视频消息传递。 对于可能听不见的人或盲人并在替代的...ganache-cli --port 8545 --gasLimit 12000000 --accounts 10 --hardfork istanbul --mnemonic brownie --fo
Boos 和 Brownie (2004) 以及 Conover 等人。 (1981) 进行了广泛的回顾。 在这里,考虑到 Boos 和 Brownie (1989) 研究的 Bartlett 检验的修改,我们开发了一个 m 文件作为方差同质性检验的替代方案。 正如Lim和...