【题解】山头狙击战

题目描述

        Lucky为了掩护大部队,单枪匹马同敌人周旋,后来被敌人包围在某山头......,不过不用怕,Lucky携带了足够的弹药,完全可以将涌上来的敌人一个一个干掉。Lucky是个神枪手,只要他的枪膛中有子弹,他就能将在他射程m(用从敌人位置到山头的直线距离算)以内的一个敌人瞬间射杀,如果在射程内没有敌人,Lucky会等待敌人靠近然后射击。但他发现了一个致命的失误:他携带的枪是单发枪,每射出一发子弹都必须花k秒钟的时间装子弹。而凶残的敌人才不会花时间等你换子弹呢。他们始终在以1m/s的速度接近山头。而如果在一个敌人到达山头时Lucky无法将他击毙,那么我们可怜的Lucky就将牺牲在敌人的刺刀下。现在Lucky向你求助:要保住自己的性命并且歼灭所有敌人,Lucky最多只能用多少时间给枪装上一发子弹?

        说明:假设一开始Lucky的枪中就有一发子弹,并且一旦确定一个装弹时间,Lucky始终会用这个时间完成子弹的装卸。希望你能帮助Lucky脱离险境。

 

输入输出格式

输入格式

        第一行,两个整数n和m(2≤n≤100000;1≤m≤10000000),n代表敌人个数,m代表Lucky的射程。

        接下来有n行,每行一个整数mi(1≤mi≤10000000),代表每个敌人一开始相对山头的距离(单位为米)。

 

输出格式

        一行,仅有一个整数,代表Lucky的换弹时间(单位为秒)。

 

输入输出样例

输入样例

6 100

236

120

120

120

120

120

 

输出样例

25

 

题解

        敌人向前进看起来很麻烦,但实际上可以转换成Lucky向前进,再结合二分答案即可。

【题解】山头狙击战
#include<iostream>
#include<algorithm>
using namespace std;
int lucky,n,m,a[100005],temp,tim,ok,mid,maxk;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int low=1,high=a[n];;)
    {
        mid=(low+high)/2;
        lucky=tim=ok=0;
        temp=1;
        while(lucky<=a[temp])
        {
            //cout<<lucky<<" "<<a[temp]<<endl;
            if(tim==1)
            {
                tim=0;
                lucky+=mid;
            }
            else 
            {
                if(a[temp]-lucky>m)
                {
                    lucky+=a[temp]-lucky-m;
                }
                tim=1;
                temp++;
                if(temp>n)
                {
                    ok=1;
                    break;
                }
            }
        }
        if(ok==1)
        {
            if(mid>maxk) maxk=mid;
            if(low+1>=high) break;
            low=mid;
        }
        else
        {
            if(low+1>=high) break;
            high=mid;
        }
        //cout<<mid<<endl;
    }
    cout<<maxk;
    return 0;
}
参考程序

 

上一篇:第11组 Alpha冲刺(1/6)


下一篇:第一次编程作业