首页 > 代码库 > 【noip模拟赛】 射击

【noip模拟赛】 射击

2024-07-15 13:58:31   215人阅读

这题似乎是什么安阳一中的模拟题，不管了，反正是学长出的noip模拟赛里面的题目。。。。

射击（shoot.pas/.c/.cpp）

时间限制：1s，内存限制128MB

题目描述：

据史书记载，对越反击战时期，有位中国侦察兵，他的代号叫814。一天他执行狙击任务，他的任务地区是n座恰巧在一条直线上的山。这些山所在直线恰巧为东西走向，山从东到西依次编号为1~n。一天814隐藏在编号为k的山上，每座山上都有1个目标。

814也非常的厉害，任务结束时杀了很多人，可是史书中只记载了两点：

1：814一定攻击了位于k号山上的目标。

2：所有被814杀死的目标所在山峰刚好从东向西高度严格递增。

请你计算：814最多杀死了多少目标。

输入描述：

第一行为两个整数N,K。

接下来是N个整数，依次表示1~n号山的高度hi。

输出描述：

814最多杀死的目标数。

样例输入：

8 6

65 158 170 299 300 155 207 389

样例输出：

4

数据范围：

30%的数据保证：0<n<=1000，0<k<=n

100%的数据，满足0<n<=200000，0<k<=n

所有数据保证h<50000。

最长上升子序列O（nlogn）算法

 

O(nlogn)的算法关键是它建立了一个数组temp[]，temp[i]表示长度为i的不下降序列中结尾元素的最小值，用top表示数组目前的长度，算法完成后top的值即为最长不下降子序列的长度。
设当前的以求出的长度为top，则判断num[i]和temp[top]：
1.如果num[i]>=temp[top]，即num[i]大于长度为top的序列中的最后一个元素，这样就可以使序列的长度增加1，即top++,然后现在的temp[top]=num[i]；
2.如果num[i]<temp[top]，那么就在temp[1]...temp[top]中找到最大的j,使得temp[j]<num[i],然后因为temp[j]<num[i]，所以num[i]大于长度为j的序列的最后一个元素，那么就可以更新长度为j+1的序列的最后一个元素，即temp[j+1]=num[i]。

 

 

 

本题算法：

 

这道题数据范围很坑！20W需要用nlogn算法，而nlogn的算法。。。。现学现卖吧。。。

我的做法有点取巧，卡时过的。。。

先做个过滤操作：前k个大于等于第k个的，过滤掉，后（n-k）个小于等于第k个的，过滤掉

然后。。。跑两遍最长上升子序列就OK啦。。

代码：

#include<cstring>#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;int f[200005];int num[200005];int temp[200005];int n,i,j,x,k;int top,ans;bool b[200005]={1};int binary_search(int x){    int mid,l=1,r=top;    while (l<=r)    {        mid=(l+r)>>1;        if (temp[mid]>=x) r=mid-1;        else        {            l=mid;            if (temp[l+1]>=x) return (l+1);                         else l++;        }        }    return 0;}void reworking(){    for (int i=1;i<=k-1;i++)    { if (num[i]>=num[k]) b[i]=false;}        for (int i=k+1;i<=n;i++)    { if (num[i]<=num[k]) b[i]=false;}}int main(){    freopen("shoot.in","r",stdin);    freopen("shoot.out","w",stdout);    for (i=1;i<=200000;i++) {b[i]=true;temp[i]=600000;}    cin>>n>>k;    for (i=1;i<=n;i++)cin>>num[i];    reworking();        memset(temp,0,sizeof(temp));    top=1; int tmp=1;    while (b[tmp]==false) tmp++;    temp[1]=num[tmp];    for (i=2;i<=k-1;i++)    {        if (b[i]==true)        {        if (num[i]>temp[top]) {temp[++top]=num[i];}        else         {            if (num[i]<temp[1]) temp[1]=num[i];            else             {                int j=binary_search(num[i]);                temp[j]=num[i];            }        }        }    }    ans=top;    memset(temp,0,sizeof(temp));    top=1;tmp=k+1;    while (b[tmp]==false) tmp++;    temp[1]=num[tmp];    for (i=k+2;i<=n;i++)    {        if (b[i]==true)        {        if (num[i]>temp[top]) {temp[++top]=num[i];}        else         {            if (num[i]<temp[1]) temp[1]=num[i];            else             {                int j=binary_search(num[i]);                temp[j]=num[i];            }        }        }    }    ans=ans+top;    cout<<ans+1<<endl;    return 0;}

结果

 


联系
我们