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.

Powered By
CHP Adblock Detector Plugin | Codehelppro