2019 计蒜之道初赛第二场 B. 百度AI小课堂-上升子序列（简单) ( 实现)-白红宇

2019 计蒜之道初赛第二场 B. 百度AI小课堂-上升子序列（简单) ( 实现)

阅读量：4677 次

发布时间：2019-06-09

本文共 2041 字，大约阅读时间需要 6 分钟。

题目背景

今天的 AI 知识小课堂的第二场开讲啦。本场 AI 知识小课堂老师教授的是数组的相关知识---上升子序列。

题目描述

给一个长度为

输入格式

输入包含多组数据。

数据的第一行为一个正整数

每组数据包括两行:

第一行包括一个正整数

第二行包括一个长度为

输出格式

对于每组数据输出一行一个整数，表示两个子序列的最小长度差。若不存在划分方案则输出

数据范围

$\le 10 , n \le 10^5 , a_i \in [ 0 , 2^{30} ]T≤10,n≤105,ai∈[0,230] 。$

特殊限制及约定：合法的划分方案数不超过

输出时每行末尾的多余空格，不影响答案正确性

样例输入复制

164 1 5 2 6 3

样例输出复制

0 思路： 紧扣题目给的特殊约定，合法的方案数不超过1个， 那么意思就是，要么没有满足条件的方案（例如 6 个数， 分别是 6 6 6 6 6 6 ）， 或者是 只有一个合法的方案数，例如样例。 这样我们从第一个数下手，如果存在一个方案，那么一定有一个lis 是以第一个数为起点的。 并且下一个比a[1] 大的数 一定被和a[1] 分在一起。 然后开始数组标记一下哪些数被分到了第一个子序列，然后剩下的子序列是否符合严格的递增的关系。 细节见代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #define ALL(x) (x).begin(), (x).end()#define rt return#define dll(x) scanf("%I64d",&x)#define xll(x) printf("%I64d\n",x)#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
                  
                   #define pll pair
                   
                    #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define db(x) cout<<"== [ "<
                    
                     <<" ] =="<
                     
                      > t; while (t--) { MS0(vis); cin >> n; repd(i, 1, n) { cin >> a[i]; } int cnt = 1; int temp = a[1]; int num = 1; repd(i, 2, n) { if (a[i] > temp) { vis[i] = 1; temp = a[i]; num++; cnt++; } } temp = -1; repd(i, 2, n) { if (vis[i] == 0) { // cout<
                      <<" "; if (temp == -1) { temp = a[i]; num++; cnt--; } if (a[i] > temp) { temp = a[i]; num++; cnt--; } } } // cout<
                       
                        = '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}