二分法与dp代码书写错误？感觉二分可能出问题

Question

嗯，简单的说，第一问可以说是求最长递减序列
只看第一问就可以

[NOIP1999 普及组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

389 207 155 300 299 170 158 65

样例输出 #1

6
2

提示

对于前 $50%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用$\mathcal O(n^2)$ 做法通过。
对于后 $50%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。

此外本题开启 spj，每点两问，按问给分。

---

$\text{upd 2022.8.24}$：新增加一组 Hack 数据。

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int a[100005]={0};
int b[100005]={0};
int ans[2]={0};
int main(){
    int len=0;
    int n=0;
    while(scanf("%d",&a[n])!=EOF){
        n++;
    }
    for(int i=0;i<n-1;i++){
        if(a[i]<=b[len])b[++len]=a[i];
        if(a[i]>b[len]){
            int mid;
            int l=0;
            int r=len;
            int as=0;
            while(l<=r){
                mid=(l+r)/2;
                if(b[mid]<a[i]){
                    r=mid-1;
                    as=mid;
                }
                if(b[mid]>=a[i]){
                    l=mid+1;
                }
            }
            b[as]=max(a[i],b[as]);
        }
    }
    ans[0]=len+1;
    vector<int>A;
    for(int i=0;i<n;i++)A.push_back(a[i]);
    while(A.size()!=0){
        int k=A[0];
        for(int i=0;i<A.size();i++){
            if(A[i]<=k){
                k=A[i];
                A.erase(A.begin()+i);
                i--;
            }
        }
        ans[1]++;
    }
    cout<<ans[0]<<endl;
    cout<<ans[1]<<endl;
    return 0;
}

另一个数据
89 126 85 103 101 86 86 98 96 99 89 81 101 92
79 77 82 97 83 100 78 72 79 97 71 80 98 89 69
74
答案
12
6
第一问有问题

Answer 1

？......你是要正确代码吗？
以下两个代码可供参考

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int f[N];
int g[N];
int h[N];
int n;

int main()
{
    while (scanf("%d", &h[n]) != EOF) n ++;
    
    int res = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ ) 
            if (h[j] >= h[i])    
                f[i] = max(f[i], f[j] + 1);
        
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        int k = 0;
        while (k < cnt && g[k] < h[i]) k ++;
        g[k] = h[i];
        if (k >= cnt) cnt ++;
    }
    
    printf("%d\n", cnt);
    
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int f[N];  //f数组存储的是最长不上升序列（注意不是子序列） 
int g[N];  //g数组存储的是最长上升序列（注意不是子序列）
int h[N];
int n;

int main() 
{
    while (cin >> h[++ n]);
    n --;
    
    int res = 1, cnt = 1;
    f[1] = g[1] = h[1];
    for (int i = 2; i <= n; i ++ ) 
    {
        if (h[i] <= f[res]) f[++ res] = h[i];
        else
        {
            int k = upper_bound(f + 1, f + res + 1, h[i], greater<int>()) - f;
            f[k] = h[i];
        }
        
        if (h[i] > g[cnt]) g[++ cnt] = h[i];
        else
        {
            int k = lower_bound(g + 1, g + cnt + 1, h[i]) - g;
            g[k] = h[i];
        }
    }
    
    printf("%d\n%d\n", res, cnt);
    
    return 0;
}

实在不会可以去看看

https://chen-ac.blog.csdn.net/article/details/119824814

这个也可以看看

https://blog.csdn.net/RIPKEY/article/details/124538097