众安笔试众安笔试题 0321

笔试时间：2025年03月21日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

街边有n个行人，每个人有一个初始朝向ai∈{0,1}。 ai=0代表他向左行走，ai=1代表她向右行走。第i个人的坐标为xi，行走速度均相同，且不存在两个人的初始位置重合。在经过了足够漫长的时间后，有一些人会相遇。一次相遇即：在某一时刻，两个人的坐标重合。现在想请你求出：有多少对人发生了相遇。

输入描述

第一行一个整数n。

接下来n行，每行两个整数，表示 xi和ai。

输出描述

输出一个整数，表示答案。

样例输入

3

1 1

2 0

3 1

样例输出

1

说明：相遇的人是1和2。其他的两对无法相遇。

参考题解

排序+二分查找。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> left, right;

    for (int i = 0; i < n; ++i) {
        int x, a;
        cin >> x >> a;
        if (a == 0)
            left.push_back(x);
        else
            right.push_back(x);
    }

    sort(left.begin(), left.end()); // 升序排列左行人

    long long count = 0;
    for (int x : right) {
        // 使用 lower_bound 寻找第一个 > x 的位置
        int index = lower_bound(left.begin(), left.end(), x) - left.begin();
        count += left.size() - index;
    }

    cout << count << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      List<Integer> left = new ArrayList<>();
      List<Integer> right = new ArrayList<>();
      
      for (int i = 0; i < n; i++) {
          int x = in.nextInt();
          int a = in.nextInt();
          if (a == 0) {
              left.add(x);
          } else {
              right.add(x);
          }
      }
      
      Collections.sort(left); // 对左行人坐标升序排序
      
      long count = 0;
      for (int x : right) {
          // 二分查找第一个大于x的坐标位置
          int index = Collections.binarySearch(left, x);
          if (index < 0) {
              index = -(index + 1); // 转换为插入点
          }
          count += left.size() - index; // 统计右侧所有左行人的数量
      }
      
      System.out.println(count);
  }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import bisect

n = int(input())

left = []
right = []

for _ in range(n):
    x, a = map(int, input().split())
    if a == 0:
        left.append(x)
    else:
        right.append(x)

left.sort()  # 升序排列左行人

count = 0
for x in right:
    index = bisect.bisect_right(left, x - 1)
    count += len(left) - index

print(count)