UVA501 Black Box 题解

#### 前言：先一如既往的吐槽一下UVa评测姬 切入正题 这道题，刚入眼：啊，一道模拟 然后敲了以下垃圾模拟代码 ```c++ #include<bits/stdc++.h> using namespace std; int ADD[30005]; int Array[100005]; int I,cnt; void add(int i) { cnt++; Array[cnt]=ADD[i]; return; } void get() { I++; sort(Array+1,Array+1+cnt); printf("%d\n",Array[I]); return; } signed main() { int T;scanf("%d",&T); while(T--) { memset(ADD,0,sizeof(ADD)); memset(Array,0,sizeof(Array)); I=cnt=0; int m,n,now=0; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { scanf("%d",&ADD[i]); } for(int i=1;i<=n;i++) { int t; scanf("%d",&t); if(now==t) { get(); continue; } while(now<t) { now++; add(now); } get(); } puts(""); } return 0; } ``` 果断TLE emmm然后分析了一下复杂度 抽了自己俩耳光 这题**显然**不能次次查询都sort 然后想到了lower_bound()插入 分析了一下复杂度是Ｏ(能过) 然后把Array换了一个vector,代码如下 ```c++ #include<bits/stdc++.h> using namespace std; int ADD[30005]; vector<int>Array; vector<int>::iterator it; int cnt; void add() { it=lower_bound(Array.begin(),Array.end(),ADD[cnt]); if(it!=Array.end()) Array.insert(it,ADD[cnt++]); else Array.push_back(ADD[cnt++]); return; } void get(int i) { printf("%d\n",Array[i]); return; } signed main() { int T;scanf("%d",&T); while(T--) { memset(ADD,0,sizeof(ADD)); Array.clear(); cnt=0; int m,n; scanf("%d%d",&m,&n); for(int i=0;i<m;i++) { scanf("%d",&ADD[i]); } for(int i=0;i<n;i++) { int t; scanf("%d",&t); while(cnt<t) add(); get(i); } puts(""); } return 0; } ``` 然后赤裸裸的WA了emmm 挠了挠头 看了一下题面 　 #### 每组输出之间用一组空行隔开 想着"多一行空行应该没什么事吧"就在puts("");前面加了一个if(T) 然后就A了emmm UVa魔鬼吧QwQ