Codeforces Round #773 (Div. 2) C. Great Sequence （桶排思维+map）

题目链接

https://codeforces.com/contest/1642/problem/C

题面

题意

T组数据，每组数据输入一个n和x，以及长度为n的 a [ i ] a[i] a[i] 数组，我们希望能将这n个数分成两堆，第一堆放在奇数位置，第二堆放在偶数位置，一一对应且 a [ i × 2 − 1 ] × x = = a [ i × 2 ] a[i \times 2-1] \times x == a[i\times 2] a[i×2−1]×x==a[i×2]，现在我们有一个操作可以添加仍以一个数，现在问你最少使用多少操作使得现在的n个数满足上述条件

思路

我们先开一个map统计每一个元素的个数，然后对数组排序，从前往后遍历，如果发现 a [ i ] × x a[i] \times x a[i]×x 的数量大于0，那么就让 map 中 a [ i ] × x a[i] \times x a[i]×x 的数量减一，如果没有的话，说明需要通过添加操作来配对了，于是此时将操作数加一，最后就统计出最少需要的操作数了,详情请看代码

代码

#include
using namespace std;

#define ll long long

const int N = 2e5+10;

ll t,n,x;

ll a[N];

void slove(){
	cin>>n>>x;
	map vis;
	for(int i = 1;i >a[i],vis[a[i]]++;
	sort(a+1,a+n+1);
	ll ans = 0LL;
	for(int i = 1;i  0)
			vis[a[i] * x]--;
		else ans++;
	}
	cout