走过路过的,救救孩子吧
查看原帖
走过路过的,救救孩子吧
758530
dsxxsd楼主2023/2/15 18:40

前十个过了,后面就全TLE了……救救孩子吧

#include<stdio.h>
#include<math.h>
int max(int, int);
int search(int*,int,int);
int dd[100003]={0};//导弹高度
int most[100003]={1};//以各导弹为结尾的最长不升子列的长度

int main(void)
{
    
    int times = 0;
    char ch;

    while (times>=0)//输入导弹高度
    { 
        scanf("%d", &dd[times++]);
        ch = getchar();
        if(ch=='\n')
            break;
    }
    for (int i = 0; i < times; i++)//初始化most为1
        most[i] = 1;

    for(int i=1;i<times;i++)//动态规划求最长
    {
        for(int j=0;j<i;j++)
        {
            if(dd[i]<=dd[j])
        {
            most[i]=max(most[i],(most[j]+1));
        } 
            else continue;
        }
    }
    
    int ans=most[0];

    for(int i=0;i<times;i++)//判断哪个不升子列最长
    {
        if(ans<=most[i])
            ans=most[i];
    }
    printf("%d\n", ans);    /*第一问结束*/
    
    int height[100000]={0,dd[0]};//各拦截系统的最大高度
    int nlj = 1;                 //拦截系统数
    for(int i=1;i<times;i++)
    {
        if(dd[i]>height[nlj]) //超出上限,需要新的拦截系统
            {
                nlj++;
                height[nlj]=dd[i];
            }
        else{                 //不需要新拦截系统,二分定位导弹由哪个拦截
                int back = search(height,nlj,dd[i]);
                height[back]=dd[i];
            }  
    }
    printf("%d", nlj);    /*第二问结束*/
    return 0;
}

int max(int a, int b)
{
    if(a>=b)
        return a;
    else 
        return b;
}//第一题两个数比大小

int search(int* first, int nlj,int inp)
{
    int low=0;   //编号下限
    int high=nlj;//编号上限

    while(high-low>1)
    {
        int mid = (low+high)/2;
        if(inp<first[mid])
            high=mid;
        else
            low=mid;     
    }
        return high;
}//第二问二分

求求了

2023/2/15 18:40
加载中...