题解 | #讨厌鬼购物#

题目链接

讨厌鬼购物

题目描述

共有 $n$ 类商品，每类商品都在 A 店和 B 店出售。第 $i$ 类商品在 A 店的价格为 $p_{a,i}$ ，评分为 $q_{a,i}$ ；在 B 店的价格为 $p_{b,i}$ ，评分为 $q_{b,i}$ 。

如果一类商品在其中一个店的价格严格小于对方，同时评分严格大于对方，那么讨厌鬼就一定会买下这类商品。请问讨厌鬼在购物完之后，一定会购买几类商品？

解题思路

本题的解法非常直接，只需根据题意模拟判断过程即可。我们需要对每一类商品进行检查，看它是否满足“一定购买”的条件。

对于第 $i$ 类商品（从 $0$ 到 $n-1$ ），它被购买的条件是以下两种情况之一：

在 A 店购买：A 店的价格更低，且评分更高。数学表达式为： $p_{a,i} < p_{b,i}$ 并且 $q_{a,i} > q_{b,i}$ 。
在 B 店购买：B 店的价格更低，且评分更高。数学表达式为： $p_{b,i} < p_{a,i}$ 并且 $q_{b,i} > q_{a,i}$ 。

这两个条件是互斥的，因为价格不可能同时 $p_{a,i} < p_{b,i}$ 和 $p_{b,i} < p_{a,i}$ 。

因此，我们只需要遍历所有 $n$ 类商品，对每一类商品检查上述两个条件是否有一个成立。如果成立，就将计数器加一。遍历结束后，计数器的值即为最终答案。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> p_a(n), p_b(n), q_a(n), q_b(n);

    for (int i = 0; i < n; ++i) cin >> p_a[i];
    for (int i = 0; i < n; ++i) cin >> p_b[i];
    for (int i = 0; i < n; ++i) cin >> q_a[i];
    for (int i = 0; i < n; ++i) cin >> q_b[i];

    int count = 0;
    for (int i = 0; i < n; ++i) {
        bool buy_from_a = (p_a[i] < p_b[i]) && (q_a[i] > q_b[i]);
        bool buy_from_b = (p_b[i] < p_a[i]) && (q_b[i] > q_a[i]);
        if (buy_from_a || buy_from_b) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] p_a = new int[n];
        int[] p_b = new int[n];
        int[] q_a = new int[n];
        int[] q_b = new int[n];

        for (int i = 0; i < n; i++) p_a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) p_b[i] = sc.nextInt();
        for (int i = 0; i < n; i++) q_a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) q_b[i] = sc.nextInt();

        int count = 0;
        for (int i = 0; i < n; i++) {
            boolean buyFromA = (p_a[i] < p_b[i]) && (q_a[i] > q_b[i]);
            boolean buyFromB = (p_b[i] < p_a[i]) && (q_b[i] > q_a[i]);
            if (buyFromA || buyFromB) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}

def solve():
    n = int(input())
    p_a = list(map(int, input().split()))
    p_b = list(map(int, input().split()))
    q_a = list(map(int, input().split()))
    q_b = list(map(int, input().split()))

    count = 0
    for i in range(n):
        buy_from_a = (p_a[i] < p_b[i]) and (q_a[i] > q_b[i])
        buy_from_b = (p_b[i] < p_a[i]) and (q_b[i] > q_a[i])
        if buy_from_a or buy_from_b:
            count += 1
            
    print(count)

solve()

算法及复杂度

算法：线性扫描
时间复杂度： $\mathcal{O}(n)$ ，因为我们需要遍历一次所有 $n$ 类商品。
空间复杂度： $\mathcal{O}(n)$ ，用于存储四组输入数据，每组数据包含 $n$ 个整数。