洛谷【数据结构1-1】线性表

P3156 【深基15.例1】询问学号

传送门

题目描述

有 n(n≤2×1^6) 名同学陆陆续续进入教室。我们知道每名同学的学号(在 1 到 10^9之间)，按进教室的顺序给出。上课了，老师想知道第 i 个进入教室的同学的学号是什么(最先进入教室的同学 i=1)，询问次数不超过 10^5次。

输入格式

第一行 2 个整数 n 和 m，表示学生个数和询问次数。

第二行 n 个整数，表示按顺序进入教室的学号。

第三行 m 个整数，表示询问第几个进入教室的同学。

输出格式

m 个整数表示答案，用换行隔开。

输入输出样例

输入 #1

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9

输出 #1

1

8

5

解题思路：这，，直接用一个数组储存，然后输出就行

code：

#include
using namespace std;
#define N 2000005
int a[N];
int n,m;
int main(void)
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i>a[i];
    while(m--)
        cin>>n,cout q;
    int t, i, j, k, p;
    while (q--)
    {
        cin >> p >> i >> j;
        if (p == 1)
        {
            cin >> k;
            a[i].s++;
            a[i].num.push_back(j);//更新num的值
            a[i].key.push_back(k);//更新key的值
        }
        else
        {
            for (int t = a[i].s; t >= 0; --t)
            {
                if (a[i].num[t] == j)//当找到j这个格子就跳出，因为前面的元素没有用了。
                {
                    cout  str;
    for (int i = 0; i < str.length(); ++i)
    {
        if (str[i] >= '0' && str[i] > m;
    for (int i = m; i  ti >> ki;
        for (int j = 1; j > temp;
            t[cnt] = temp;
            KI[cnt++] = ti;
            if (!X[temp])//如果temp的国籍人数为0，sum自增
                sum++;
            X[temp]++;
        }
        while (ti - KI[ct] >= 86400)//要用while循环，因为时间差可能好几个都大于86400
        {
            X[t[ct]]--;
            if (!X[t[ct]])//如果该乘客的国籍人数为0，国籍总数就--
                sum--;
            ct++;
        }
        cout  ch;
    for (int i = 0; i = 0; --j)
            {
                if (!is[j] && ch[j] == '[')//如果匹配
                {
                    is[i] = is[j] = 1;//标记
                    break;//注意要跳出
                }
                else if (!is[j] && ch[j] == '(')//不匹配
                {
                    break;//直接跳出，不用看前面的！！！，这点太坑了T^T
                }
            }
        }
        else if (ch[i] == ')')//同上
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (!is[j] && ch[j] == '(')
                {
                    is[i] = is[j] = 1;
                    break;
                }
                else if (!is[j] && ch[j] == '[')
                {
                    break;
                }
            }
        }
    }
    for (int i = 0, len = strlen(ch); i < len; ++i)
    {
        if (is[i])//如果标记了，那么肯定能组合成一个完整的左右括号
            putchar(ch[i]);
        else
        {
            if (ch[i] == '(' || ch[i] == ')')//输出完整的左右括号
                printf("()");
            else if (ch[i] == '[' || ch[i] == ']')
                printf("[]");
        }
    }
    return 0;
}

当然上面的是O(n^2)的时间复杂度，我们可以想想优化，我们要搜索左边第一个左括号，其实不用遍历去搜索

我们把每次读到的左括号放进一个栈里面，每次匹配的时候拿出来比较就行。复杂度O(n)

code:

#include 
#include 
#include 
#include 
int is[105];
char ch[105];
using namespace std;
int main(void)
{
    ios::sync_with_stdio(false);
    stack last;
    stack loc;
    cin >> ch;
    int len = strlen(ch);
    for (int i = 0; i < len; ++i)
    {
        if (ch[i] == '(' || ch[i] == '[')
            last.push(ch[i]), loc.push(i);
        else
        {
            if (ch[i] == ')')
            {
                if (last.size())
                {
                    if (last.top() == '(')
                    {
                        is[i] = is[loc.top()] = 1;
                        loc.pop();
                        last.pop();
                    }
                }
            }
            else if (ch[i] == ']')
            {
                if (loc.size())
                {
                    if (last.top() == '[')
                    {
                        is[i] = is[loc.top()] = 1;
                        loc.pop();
                        last.pop();
                    }
                }
            }
        }
    }
    for (int i = 0; i < len; ++i)
    {
        if (is[i])
            cout > n;
        for (int i = 1; i > a[i];
        for (int i = 1; i > b[i];
        int i, j;
        for (i = 1, j = 1; i