【noip模拟赛】射击

时间：2014-08-03 20:23:15 阅读：364 评论：0 收藏：0 [点我收藏+]

这题似乎是什么安阳一中的模拟题，不管了，反正是学长出的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

样例输出：

数据范围：

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;
}