首页 > 试题广场 >

小红扔桃子

[编程题]小红扔桃子

热度指数：316 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在平面直角坐标系中，小红总共扔了 $n$ 个桃子，第 $i$ 个桃子的坐标是 $x_i,y_i$ 。对于任意两个桃子而言，如果它们在同一行或同一列，则小红可以获得1分。（对于同一个坐标的两个桃子也只能获得1分）。
小红想知道，自己最终获得了多少分？

输入描述:

第一行输入一个正整数，代表小红扔的桃子数量。
接下来的行，每行输入两个正整数，代表每个桃子的坐标。

输出描述:

一个整数，代表最终的分数。

示例1

输入

输出

说明

第一个桃子和第二个桃子获得1分。
第二个桃子和第三个桃子获得1分。

示例2

输入

输出

说明

共有以下的“桃子对”可以获得分数：[1,2],[1,3],[2,3],[4,5]

算法知识视频讲解

梅老板的粉

哈希表

使用哈希表记录出现在每个横轴位置和纵轴位置的坐标总数。
分别记录 x 轴相同的位置和 y 轴相同位置的得分。
最后对于位于相同位置的桃子，需要减去这些桃子组合的得分，因为重复计算了。

时间复杂度： $\mathcal{O(nlogn)}$

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int64_t> xmap;
    unordered_map<int, int64_t> ymap;
    map<pair<int, int>, int64_t> myMap;
    while (n--) {
        int x, y;
        cin >> x >> y;
        xmap[x]++;
        ymap[y]++;
        myMap[ {x, y}]++;
    }
    int64_t ret = 0;
    // printf("start....\n");
    for (auto& e : xmap) {
        if (e.second > 1) {
            int64_t tmp = (e.second * (e.second - 1));
            // // printf("横坐标在 %d 位置的数量为: %d, 得分: %d\n", e.first,
            //        e.second, tmp);
            ret += tmp / 2;
        }
    }
    for (auto& e : ymap) {
        if (e.second > 1) {
            int64_t tmp = (e.second * (e.second - 1));
            // printf("纵坐标在 %d 位置的数量为: %d, 得分: %d\n", e.first,
            //    e.second, tmp);
            ret += tmp / 2;
        }
    }
    for (auto& e : myMap) {
        if (e.second > 1) {
            int64_t tmp = (e.second * (e.second - 1));
            // printf("在位置(%d, %d)位置的数量为: %d, 得分: %d\n", e.first.first,
            //    e.first.second, e.second, tmp);

            ret -= tmp / 2;
        }
    }
    std::cout << ret << std::endl;
    return 0;

}
// 64 位输出请用 printf("%lld")

发表于 2023-03-16 00:32:08 回复(0)

牛客985204682号

#include <functional>

#include <iostream>

#include <unordered_map>

#include <utility>

using namespace std;

struct func {

size_t operator()(const pair<int, long>& p)const {

return hash<int>()(p.first)^hash<int>()(p.second);

}

};

unordered_map<int, long> ux, uy;

unordered_map<pair<int, long>, int, func> umap;

int main() {

int n;

cin >> n;

long res = 0;

while (n--) {

int x, y;

cin >> x >> y;

res += ux[x];

res += uy[y];

res -= umap[ {x, y}];

ux[x]++;

uy[y]++;

umap[ {x, y}]++;

}

cout << res;

}

// 64 位输出请用 printf("%lld")

发表于 2023-03-18 17:22:59 回复(0)

XXXXXXin425

n = int(input())

x_dic, y_dic, coor_dic = {}, {}, {}
res = 0
for _ in range(n):
    x, y = list(map(int, input().split()))
    if x not in x_dic:
        x_dic[x] = 0
    if y not in y_dic:
        y_dic[y] = 0
    if (x,y) not in coor_dic:
        coor_dic[(x,y)] = 0
    res += (x_dic[x]+y_dic[y]-coor_dic[(x,y)]) 
    x_dic[x] += 1
    y_dic[y] += 1
    coor_dic[(x,y)] += 1
print(res)

发表于 2023-03-15 22:53:57 回复(0)

__what__

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

Map<Long,Integer> xIndexs = new HashMap<>();

Map<Long,Integer> yIndexs = new HashMap<>();

Map<String,Integer> point = new HashMap<>();

Long res = 0L;

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

Long flag = 0L;

Long x = in.nextLong();

Long y = in.nextLong();

if(xIndexs.containsKey(x)) flag += xIndexs.get(x);

if(yIndexs.containsKey(y)) flag += yIndexs.get(y);

xIndexs.put(x,xIndexs.getOrDefault(x,0)+1);

yIndexs.put(y,yIndexs.getOrDefault(y,0)+1);

if(point.containsKey(x+" "+y)) flag -= point.get(x +" "+ y);

point.put(x+" "+y,point.getOrDefault(x+" "+y,0)+1);

res += flag;

}

System.out.print(res);

}

//笨办法

发表于 2023-03-15 11:47:38 回复(0)

提交观点

问题信息

来自：22年秋招蚂蚁编程题精选

难度：

4条回答 10收藏 1365浏览

小红扔桃子

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

哈希表

问题信息

热门推荐

相关试题