CodeForces 275C k-Multiple Free Set（2分）

CodeForces 275C k-Multiple Free Set（二分）

题目链接：CodeForces 275C k-Multiple Free Set

题目大意：给出n和k，然后给出元素个数为n的集合num，现在要从num集合中挑选出尽量多的元素组成新的集合，新的集合的要求是集合中不存在元素x ， y（x < y）使得x * k = y，输出最大的元素个数。

解题思路：将num数组排序，对应每个数值的num[i] * k进行二分搜索，如果搜索到，cnt--。

这里有两个坑点：

1、因为x < y，所以要考虑k = 1的情况。

2、数据

5 2 1 2 3 4 5，自己去发现问题吧。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 100005;
int n, cnt, vis[N];
long long k, num[N];

void search(long long c) {
	int l = -1, r = n;
	while (l < r) {
		int mid = (l + r) / 2;
		if (num[mid] < c) l = mid;
		else if (num[mid] > c) r = mid;
		else { 
			if (c / k < num[mid]) {
				vis[mid] = 1;
				cnt--; 
			}
			return; 
		}
		if (l == r - 1) return;
	}
}

int main () {
	scanf("%d%lld", &n, &k);

	cnt = n;
	for (int i = 0; i < n; i++)
		scanf("%lld", &num[i]);
	memset(vis, 0, sizeof(vis));

	sort(num, num + n);

	if (k != 1)
		for (int i = 0; i < n; i++) {
			if (vis[i]) continue;
			search(num[i] * k);
		}
	printf("%d\n", cnt);
	return 0;
}