思路:
- 最后转化成一个链, 然后贪心地从链的一端处理即可!
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define M 2000005 #define ri register int long long p[M],q[M],vis[M]; int T; int n,m; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>T; while(T--) { cin>>n>>m; map<long long,int> mp; for(ri i=1;i<=n;i++) { cin>>p[i]; mp[p[i]]++; } sort(p+1,p+1+n); n=unique(p+1,p+1+n)-p-1; long long ans=0; for(ri i=1;i<=n;i++) { if(mp[p[i]]==0) continue; int tmp=min(mp[p[i]],mp[p[i]*m]); mp[p[i]]-=tmp; mp[p[i]*m]-=tmp; ans+=mp[p[i]]; } cout<<ans<<"\n"; } return 0; }View Code
标签:Great,Sequence,int,cin,long,CF2,ri,贪心 From: https://www.cnblogs.com/Lamboofhome/p/16873028.html