题意:
长度为n的数组,需要数组里所有数成两两一对,满足a * x = p 的关系,求最少需要添加多少个数,才能满足这个条件。
思路:
整体看来就是将数组内能成对的个数先减掉,剩下的个数就是要添加的数的个数。
#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;template<typename T>inline void rd(T &a) {char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};const int N = 2e5+10;int a[N];
void solve()
{map<int, bool> mp; //int n, x;cin >> n >> x;for(int i =1; i <= n; i ++) rd(a[i]);sort(a+1, a+1+n);int j = n - 1;int ans = n;for(int i = n; i >= 1; i --){if(mp[i]) continue; //已经访问过if(a[i] % x == 0){int temp = a[i] / x;// 需要保证当前算到的约数比temp大// 并且保证没有访问过 如果访问过那么循环继续(mp[j] == true)while (j >= 1 && (mp[j] == true || a[j] > temp)){j--;}if(j >= 1 && a[j] == temp && !mp[j]){mp[j] = true, mp[i] = true;ans -= 2;}}}cout << ans << endl;
}int main()
{int T;cin >> T;while (T--){solve();}
}
更多推荐
Great,Sequence
发布评论