首页 > 试题广场 >

争夺地盘

[编程题]争夺地盘

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

A国和B国正在打仗，他们的目的是n块土地。现在，A国和B国暂时休战，为了能合理分配这一些土地，AB国开始协商。

A国希望得到这n块土地中的p块土地，B国希望得到这n块土地中的q块土地。每个国家都将自己希望得到的土地编号告诉了小团和小美——两位战争调和人。

你需要帮小团和小美计算，有多少块土地是只有A国想要的，有多少块土地是只有B国想要的，有多少块土地是两个国家都想要的。

输入描述:

输入第一行包含三个整数n,p,q，含义如题意所示

接下来一行p个整数，空格隔开，第i个整数代表A国需要的土地编号 $a_i$

接下来一行q个整数，空格隔开，第i个整数代表B国需要的土地编号 $b_i$

土地编号从q开始，n结束。

输出描述:

输出包含三个数，只有A国想要的土地数，只有B国想要的土地数，两个国家都想要的土地数。

示例1

输入

5 3 3
1 2 3
3 4 5

输出

2 2 1

说明

1,2号土地只有A想要，4,5号土地只有B想要，3号土地都想要

备注:

对于40%的数据， $n,p,q\leq 1000$

对于100%的数据， $p,q\leq n\leq 100000, 1\leq a_i, b_i, \leq n$ ,数据保证所有的 $a_i$ 互相不相同， $b_i$ 互相不相同。

算法知识视频讲解

柠致

JS版本，使用双指针，降低时间复杂度

var str1 = readline()
var str2 = readline()
var str3 = readline()

let p = parseInt( str1.split(' ')[1] ) - 1
let q = parseInt( str1.split(' ')[2] ) - 1

const A = str2.split(' ').map(v => parseInt(v))
const B = str3.split(' ').map(v => parseInt(v))
A.sort((a,b) => a-b)
B.sort((a,b) => a-b)

let a = 0, b = 0, c = 0
while(p>=0 && q>=0) {
    if(A[p] === B[q]) {
        c++
        p--
        q--
    } else if(A[p] > B[q]) {
        p--
        a++
    } else {
        q--
        b++
    }
}
if(p>=0) {
    a += p+1
} else if(q>=0) {
    b += q+1
}

console.log(a, b, c)

发表于 2021-08-15 21:06:37 回复(0)

_叶知秋

思路：只需要统计两者都要的地的数量，然后做减法就可得到只有A/B要的地。

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int p = Integer.parseInt(params[1]);
        int q = Integer.parseInt(params[2]);
        // 记录A是否要某块地
        boolean[] wanted = new boolean[n+1];
        int[] a = new int[p+1];
        int[] b = new int[q+1];
        params = br.readLine().trim().split(" ");
        for(int i=1;i<=p;++i){
            a[i] = Integer.parseInt(params[i-1]);
            wanted[a[i]] = true;
        }
        params = br.readLine().trim().split(" ");
        int both=0;
        for(int i=1;i<=q;++i){
            b[i] = Integer.parseInt(params[i-1]);
            // 如果B要的A也要，就是两者都想要
            if(wanted[b[i]]){
                both++;
            }
        }
        // onlyA = p-both
        // onlyB = q-both
        System.out.println((p-both)+" "+(q-both)+" "+both);
    }
}

发表于 2022-03-07 10:58:06 回复(0)

pein531

分别将A国和B国想要的土地编号存入两个集合中，然后计算交集的数量，就是两个国家都想要的土地数量。A集合的大小减去交集数量就是只有A想要的土地数量，B集合的大小减去交集数量就是只有B想要的土地数量。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int p = Integer.parseInt(params[1]);
        int q = Integer.parseInt(params[2]);
        HashSet<Integer> wantedA = new HashSet<>();
        HashSet<Integer> wantedB = new HashSet<>();
        params = br.readLine().trim().split(" ");
        for(int i = 0; i < params.length; i++)
            wantedA.add(Integer.parseInt(params[i]));
        // 计算交集的数量
        int commonCount = 0;
        params = br.readLine().trim().split(" ");
        for(int i = 0; i < params.length; i++){
            wantedB.add(Integer.parseInt(params[i]));
            if(wantedA.contains(Integer.parseInt(params[i]))) commonCount ++;
        }
        System.out.println(wantedA.size() - commonCount + " " + (wantedB.size() - commonCount) + " " + commonCount);
    }
}

发表于 2021-03-02 18:01:15 回复(4)

来自蓝星

#include <iostream>
#include <set>
#include <vector>
 
using namespace std;
 
int main() {
    int  n,a,b;
    cin>>n>>a>>b;
    set<int> sA;
    for(int i = 0; i < a; i++) {
        int s;
        cin >> s;
        sA.insert(s);
    }
    // set<int> sA(vA.begin(), vA.end());
    vector<int> vB(b, 0);
    for(int i = 0; i < b; i++) {
        cin >> vB[i];
    }
     
    int ab_common = 0;
    for(int i = 0; i < b; i++) {
        if(sA.count(vB[i]))
            ab_common+=1;
    }
    int a_real = a - ab_common;
    int b_real = b - ab_common;
    cout<<a_real<<" "<<b_real<<" "<<ab_common;
     
    return 0;
}

发表于 2022-09-10 10:22:16 回复(0)

牛客833845976号

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] t = new int[2];
        t[0] = sc.nextInt();
        t[1] = sc.nextInt();

        int[] arr = new int[n+1];
        
        for (int i = 0; i < 2; i++) {
            int num = 0;
            for (int j = 1; j <= t[i]; j++) {
                num = sc.nextInt();
                arr[num] += (i+1);
            }
        }
        
        int l = 0;
        int m = 0;
        int r = 0;
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 1) {
                l++;
            }else if (arr[i] == 2) {
                r++;
            }else if (arr[i] == 3) {
                m++;
            }
        }
        System.out.println(l + " " + r + " " + m);
    }
}

发表于 2022-07-28 18:26:44 回复(0)

Python

牛客991389689号

meta = input()
n,p,q = map(int,meta.split())
P_int = input()
Q_int = input()

a_dict = {int(i):1 for i in P_int.split()}
b_dict = {int(i):1 for i in Q_int.split()}

num_A = 0
num_B = 0
num_AB = 0


for i in range(1,n+1,1):
    if  (a_dict.get(i,None)) and (b_dict.get(i,None)):
        num_AB +=1
    elif (a_dict.get(i,None)) and (not b_dict.get(i,None)):
        num_A +=1
    elif (not a_dict.get(i,None)) and (b_dict.get(i,None)):
        num_B +=1

print(num_A,num_B,num_AB)

发表于 2022-05-12 20:07:34 回复(0)

牛客123456789.号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        int q = in.nextInt();
        Set<Integer> ans = new HashSet<Integer>();
        int count = 0;
        for (int i = 0; i < p; i++) {
            ans.add(in.nextInt());
        }
        for (int i = 0; i < q; i++) {
            int b = in.nextInt();
            if (ans.contains(b)) {
                count++;
            }
        }
        System.out.println((p - count) + " " + (q - count) + " " + count);
    }
}

发表于 2022-04-29 20:32:48 回复(0)

jsysisnz

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int p=sc.nextInt();
            int q=sc.nextInt();
            Set<Integer> set=new HashSet();
            int count=0;
            for(int i=0;i<p+q;i++){
                if(!set.add(sc.nextInt())){
                    count++;
                }
            }
            System.out.println((p-count)+" "+(q-count)+" "+count);
        }
    }
}

发表于 2021-08-26 11:12:12 回复(0)

chenjiag

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String[] str = in.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int p = Integer.parseInt(str[1]);
        int q = Integer.parseInt(str[2]);
        int all = 0;
        HashMap<Integer, Integer> need = new HashMap<>();
        String[] A = in.nextLine().split(" ");
        String[] B = in.nextLine().split(" ");
        for (String s : A) {
            int temp = Integer.parseInt(s);
            need.put(temp, need.getOrDefault(temp, 0) + 1);
        }
        for (String s : B) {
            int temp = Integer.parseInt(s);
            if (need.containsKey(temp)) {
                all++;
            }
        }
        System.out.println((p - all) + " " + (q - all) + " " + all);

    }
}

发表于 2021-06-07 20:16:14 回复(0)

JavaScript

hahbat

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
var K = 3;
var input = [];
rl.on('line', function (line) {
    input.push(line);
    if (input.length == K) {
        var result = deal(input).join(' ');
        console.log(result)
        input = []
    }
});

function deal(data) {
    let [num, arr1, arr2] = data.map(arr => {
        return arr.split(' ').map(item => parseInt(item))
    })
    let m = new Map()
    let res = [num[1], num[2], 0]
    for (let i = 0; i < arr1.length; i++) {
        if (!m[arr1[i]]) {
            m[arr1[i]] = true
        }
    }
    for (let i = 0; i < arr2.length; i++) {
        if (m[arr2[i]]) {
            res[0]--
            res[1]--
            res[2]++
        }
    }
    return res
}

发表于 2021-05-08 22:05:29 回复(0)

牛客213998571号

n, p, q = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
result = [0, 0, 0]
c=len(list(set(b).intersection(set(a))))
result[2] = c
result[0] = len(a)-c
result[1] = len(b)-c
        
result = str(result).replace("[","").replace("]","").replace(",","").replace(" "," ")
print(result)

发表于 2021-03-23 20:59:49 回复(1)