注意10^9 * 10^9会整形溢出,所以队列存的数不能int类型,得是long long类型;
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int ans = -1;
queue<long long> ansque;
int n;
vector<int> tempvec;
int p;
int main() {
cin >> n >> p;
if (n == 0||p==0) {
cout << 0;
return 0;
}
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
tempvec.push_back(temp);
}
sort(tempvec.begin(), tempvec.end());
ansque.push(tempvec[0]);
ans = 1;
for (int i = 1; i < tempvec.size(); i++)
{
if (ansque.front()*p >= tempvec[i]) {
ansque.push(tempvec[i]);
}
else
{
while (!ansque.empty() && ansque.front()*p <= tempvec[i]) {
ansque.pop();
}
ansque.push(tempvec[i]);
}
if (ansque.size() > ans) {
ans = ansque.size();
}
}
cout << ans;
return 0;
}
不借助队列,简洁版本
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
long long p;
scanf("%d%lld", &n, &p);
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
sort(v.begin(), v.end());
int result = 0, temp = 0;
for (int i = 0; i < n; i++) {
for (int j = i + result; j < n; j++) {
if (v[j] <= v[i] * p) {
temp = j - i + 1;
if (temp > result)
result = temp;
} else {
break;
}
}
}
cout << result;
return 0;
}