题解 CF1238B 【Kill 'Em All】

· · 题解

贪心可过！

读题：

一个水平的坐标轴，怪兽都在原点右边，若使得怪物到达原点右边，则怪兽死亡。

当在c点发射导弹，则：

  2. y<c$：怪兽向左移动r个单位，坐标变为 $y -r
  3. y>c$：怪兽向右移动r个单位，坐标为$y+r

    为了杀死怪兽，至少要发射多少导弹。

思路：

贪心,因为怪物被打到0的左端，就会KO，所以我们每一炮都要轰到怪物的右边。 完整思路如下：
把怪物按照坐标位置从大到小排序，每次炮轰坐标最大的怪物。循环到每一个怪物时，只需判断它是否已经死在0左边，若没有，就再打它一炮，计数器加一；否则退出循环，因为如果该怪被轰到左边，坐标比它小的所有怪物一定都已经KO了，结束。

上代码：

# include<bits/stdc++.h>
using namespace std;
int a[100000];
int main () {
    int t,n,m,ans=0,now=-99999,num=0;
    cin>>t;
    for(int i=1; i<=t; i++) {
        ans=0;
        num=0;
        now=-999999;
        cin>>n>>m;
        for (int j=1; j<=n; j++)
            cin>>a[j];
        sort (a+1,a+1+n);
        for (int j=n; j>=1; j--) {
            if(a[j]==now)
                continue;
            if(a[j]-num<=0)
                break;
            ans++;
            num+=m;
            now=a[j];
        }
        cout<<ans<<endl;
    }
    return 0;
}