Doveqise

Doveqise

万事皆虚,诸行皆允

UVA501 Black Box 题解

posted on 2019-05-21 20:18:10 | under 题解 |

前言:先一如既往的吐槽一下UVa评测姬

切入正题
这道题,刚入眼:啊,一道模拟
然后敲了以下垃圾模拟代码

#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()插入
分析了一下复杂度是O(能过)
然后把Array换了一个vector,代码如下

#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