Question Name:BEAUTIFUL PAIRS

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

int n;
int cntA[1001];
int cntB[1001];

int MAIN()
{
	memset(cntA, 0, sizeof(cntA));
	memset(cntB, 0, sizeof(cntB));
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int t;
		cin >> t;
		cntA[t] ++;
	}
	for(int i = 1; i <= n; i++)
	{
		int t;
		cin >> t;
		cntB[t] ++;
	}
	int ans = 0;
	for(int i = 1; i <= 1000; i++)
		ans += min(cntA[i], cntB[i]);
	if(ans == n)
		ans --;
	else
		ans ++;
	cout << ans << endl;
	
	return 0;
}

int main()
{
	int start = clock();
	#ifdef LOCAL_TEST
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cout << fixed << setprecision(16);
	int ret = MAIN();
	#ifdef LOCAL_TEST
		cout << "[Finished in " << clock() - start << " ms]" << endl;
	#endif
	return ret;
}
  • Problem Description
    You are given two arrays, A and B, both containing N integers.

    A pair of indices (i,j) is beautiful if the ith element of array A is equal to the jth element of array B. In other words, pair (i,j) is beautiful if and only if Ai=Bj. 

    Given A and B, there are k pairs of beautiful indices (i0,j0),…,(ik-1,jk-1). A pair of indices in this set is pairwise disjoint if and only if for each 0<=x<=y<=k-1 it holds that ix not equal to iy and jx not equal to jy.

    Change exactly 1 element in B so that the resulting number of pairwise disjoint beautiful pairs is maximal, and print this maximal number to stdout.

    Input Format:
    The first line contains a single integer, N (the number of elements in A and B). 
    The second line contains N space-separated integers describing array A. 
    The third line contains N space-separated integers describing array B.

    Constraints
    1<=N<=10^3
    1<= Ai<=10^3
    1<= Bi <=10^3

    Output Format:

    Determine and print the maximum possible number of pairwise disjoint beautiful pairs.
    Note: You must first change 1 element in B, and your choice of element must be optimal.
  • Test Case 1
    Input (stdin)3
    1 2 2
    1 2 3
    Expected Output3
  • Test Case 2
    Input (stdin)3
    1 2 2
    1 3 2
    Expected Output3

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.