【Ural1028】【Vijos1066】弱弱的战壕

来源和评测点

Problem Author: Pavel Zaletsky
Problem Source: Ural Collegiate Programming Contest ‘99
Ural1028
Vijos1066

题目

【题目大意】
永恒和mx正在玩一个即时战略游戏,名字嘛~~恕本人记性不好,忘了。
mx在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,
射程可以达到无限。但是,战壕有一个弱点,就是只能攻击它的左下方,
说白了就是横纵坐标都不大于它的点(mx:“我的战壕为什么这么菜”ToT)。
这样,永恒就可以从别的地方进攻摧毁战壕,从而消灭mx的部队。
战壕都有一个保护范围,同它的攻击范围一样,
它可以保护处在它左下方的战壕。
所有处于它保护范围的战壕都叫做它的保护对象。
这样,永恒就必须找到mx的战壕中保护对象最多的点,从而优先消灭它。
现在,由于永恒没有时间来计算,所以拜托你来完成这个任务:
给出这n个战壕的坐标xi、yi,要你求出保护对象个数为0,1,2……n-1的战壕的个数。
【输入格式】
第一行,一个正整数n(1<=n<=15000)
接下来n行,每行两个数xi,yi,代表第i个点的坐标
(1<=xi,yi<=32000)
注意:可能包含多重战壕的情况(即有数个点在同一坐标)
【输出格式】
输出n行,分别代表保护对象为0,1,2……n-1的战壕的个数。
【输入样例】
5
1 1
5 1
7 1
3 3
5 5
【输出样例】
1
2
1
1
0

分析

做做难度不大但有所创新的题目还是挺好的
先排序一遍确保形如这样

1
2
3
* -
**** *****
* ***** ***

按顺序处理就保证了y更小
接着用树状数组维护x的前缀和即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Zory-2017
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=15000;
//*******************全局定义*******************
struct pt
{
int x,y;
}p[MAXN+10];
//*******************接口*******************
int lowbit(int x) {return x&-x;}
int s[32000+10];
void add(int f)
{
while(f<=32001)
{
s[f]+=1;
f+=lowbit(f);
}
}
int ask(int r)
{
int sum=0;
while(r>0)
{
sum+=s[r];
r-=lowbit(r);
}
return sum;
}
//*******************主函数*******************
bool cmp(pt a,pt b)
{
if(a.y==b.y) return a.x<=b.x;
return a.y<=b.y;
/*
* -
**** *****
* ***** ***
*/
}
int ans[MAXN+10];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++)
{
ans[ask(p[i].x+1)]++;
add(p[i].x+1);
}
for(int i=0;i<=n-1;i++) printf("%d\n",ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/弱弱的战壕.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%