https://codeforces.com/contest/1238/problem/B
很容易想到从最右边开始炸,但是实现有点问题:1.要排序,2.要去重。
unique函数:
iterator unique(it1,it2):将已排好序的[it1,it2)中不同的元素提到前面,相同的元素放到后面,并返回去重后容器末尾元素的后一个迭代器。
先排序再去重,时间复杂度为。
这道题也可以用set做:
从大到小排序的set:
set<int,greater<int> >(类比优先队列)。
可以这样:
while(!s.empty()){
cout<<*s.begin();
s.erase(s.begin());
}
但是如果删掉末尾的元素就不行了,因为end是超尾迭代器,要用一个迭代器指向end前面的那个元素。
erase方法:
iterator erase(it):删除it指向的元素,返回it后面的迭代器。
iterator erase(it1,it2):删除[it1,it2)中的元素,并返回it2。
#include<bits/stdc++.h>
using namespace std;
int q;
int n,r;
int x[100010];
int main(){
scanf("%d",&q);
while(q--){
int res=0;
int zero=0;
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++){
scanf("%d",&x[i]);
}
sort(x,x+n,greater<int>());
n=unique(x,x+n)-x;
for(int i=0;i<n;i++){
if(zero>=x[i]) break;
zero+=r;
res++;
}
printf("%d\n",res);
}
return 0;
}