Datahub
数据改变生活

数星星

发表时间:2022-10-27 20:40

数星星

问题描述

小粽今晚在数星星。

小粽把整个天空看作一个平面,她测出了她看见的每个星星的坐标,第 ii 颗星星的坐标为 (xi,yi)(xi,yi)。

光数星星实在是太无聊了,小粽想知道,对于每颗星星,其左下方的星星的数量,即对于每个 ii,小粽想要知道满足 j≠ij≠i,且 xj≤xi,yj≤yixj≤xi,yj≤yi 的 jj 的数量。

输入格式

第一行一个正整数 nn,表示星星的数量。

接下来 nn 行,每行两个正整数 xi,yixi,yi,表示第 ii 颗星星的坐标。

输格式

输出共 nn 行,每行输出一个正整数,表示第 ii 颗星星左下方星星的数量。

输入样例 1

5

11

51

71

33

55

输样例 1

样例 2

点此下载。

数据规模及约定

对于 30%30% 的数据有 n≤500n≤500; 对于 60%60% 的数据有 n≤8000n≤8000;

对于 100%100% 的数据有 n≤3×105n≤3×105,所有坐标都在 int 范围内,不存在两个不同的点有相同的坐标。

提示

[回想一下归并求逆序对咋做的?你就会做这个题辣] [有兴趣的同学百度二维偏序~]

代码

#include <cstdio> #include <algorithm>

#pragma warning(disable:4996); #define maxn 500000

using namespace std;

struct Point {

int x, y, id;

void read(int id)

{

this->id = id;

scanf("%d%d", &x, &y);

}

// 先比较x轴,再比较y轴

bool operator < (const Point &a) const {

return x == a.x ? y < a.y : x < a.x;

}

};

// a: 原数组

// b: 归并辅助数组

Point a[maxn + 10], b[maxn + 10];

// ans: ans[i] 表示第 i 个点左下方的点的数目int ans[maxn + 10];

/* ========== 代码实现开始 ========= */

void solve(int l, int r)

{

if (l >= r)

return;

int m = l + r >> 1;

solve(l, m);

solve(m + 1, r);//分治,解决子问题

//归并过程

int t1 = l, t2 = m + 1, t = l;

while (t1 <= m && t2 <= r){

if (a[t1].y <= a[t2].y) {//归并

b[t++] = a[t1++];

}

else {

ans[a[t2].id] += t1 - l;//除了正常的归并外,还需统计左侧对右侧的贡献

b[t++] = a[t2++];

}

}

for (int i = t1; i <= m; i++) {

b[t++] = a[t1++];

}

for (int i = t2; i <= r; i++) {

ans[a[t2].id] += t1 - l;//除了正常的归并外,还需统计左侧对右侧的贡献

b[t++] = a[t2++];

}

for (int i = l; i <= r; i++)

a[i] = b[i];

}

// solve 被调用后,ans 数组应被计算好void solve(int n)

{

sort(a, a + n);

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

ans[i] = 0;

solve(0, n - 1);

}

/* ========== 代码实现结束 ========= */

int main()

{

int n;

scanf("%d", &n);

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

a[i].read(i);

solve(n);

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

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

return 0;


上一篇匹配
下一篇循环节
文章分类: 数据结构例题
分享到:
QQ:258506508                                     联系电话:020-000000    000-000000                                   联系邮箱:xxx@.co.m                                     联系地址:XXX省XXX市XXX县XXX路