pta实验五

2025 年 11 月 14 日

13 次浏览

暂无评论

593字数

c++

实验五

一. 7-1 部分排序

对于一组数据，我们可以只对原先处在中间位置的那些元素进行排序。

输入格式:

在一行内输入n r a1 a2 ... an

其中，不大于200的正整数n表示该组数据的个数；不大于200的非负整数r表示该组数据两端各自留有r个数不参与排序，若r+r>=n，则该组数据无需排序。

整数a1 a2 ... an是该组的n个数据，且都在8位以内。

输出格式:

排序之后的序列，元素之间用一个空格间隔，最后一个元素之后不加空格。

输入样例:

5 1 6 5 4 3 2

输出样例:

6 3 4 5 2

参考答案：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,r;
    cin>>n>>r;
    vector<int>ivec;
    int num;
    for(int i=0;i<n;i++){
         cin>>num;
        ivec.push_back(num);

    }
    if(r+r<n){
        sort(ivec.begin()+r,ivec.begin()+n-r);
    }
    bool isHead = true;
    for(auto &c:ivec){
        if(isHead){
            cout<<c;
            isHead = !isHead;
        }
        else{
            cout<<" "<<c;
        }
    }
    cout<<endl;
    return 0;
}

二. 7-2 组最大数

设有n个正整数，将他们连接成一排，组成一个最大的多位整数。

如:n=3时，3个整数13,312,343连成的最大整数为34331213。

如:n=4时，4个整数7,13,4,246连接成的最大整数为7424613。

输入格式:

有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。

输出格式:

每组数据输出一个表示最大的整数。

输入样例:

输出样例:

12312
7424613

参考答案：

#include<iostream>
#include<vector>
using namespace std;
bool compare(int a,int b){
    string sa = to_string(a);
    string sb = to_string(b);
    return sa + sb > sb + sa;  
}
int main(){
    int n;
    while(cin>>n){
        vector<int>ivec;
         int num;
        for(int i=0;i<n;i++){
            cin>>num;
            ivec.push_back(num);
        }
        sort(ivec.begin(),ivec.end(),compare);
        for(auto &s:ivec){
            cout<<s;
        }

        ivec.clear();
        cout<<endl;
    }
    return 0;
}

三. 7-3 办事大厅排队

在郑州大学综合办事大厅，每天陆陆续续有很多人来排队办事。现在你能否写程序帮助老师时刻了解当前办理业务的情况。

请同学们学习C++ STL中 list相关内容后，编程实践。

输入格式:

第一行一个数字N，表示排队信息或者查询信息条目的数量。

以下N行，每行的内容有以下3种情况

(1) in name 表示名字为name的人员新来到办事大厅，排在队伍的最后。（in和name间存在一个空格，name是名字对应字符串，长度不超过10）。

(2) out 表示当前排在最前面的人已经办理完业务，离开了。

(3) q 表示一次查询，请输出当前正在办理业务的人，也就是队伍的第1个人。如果当前无人办理业务，则输出“NULL”，不包括引号。

输出格式:

请根据以上信息，每次遇到查询时，对应一行输出。如果这时队伍有人，则输出第一个人的姓名，否则输出NULL。

输入样例:

5
in A
out
q
in B
q

输出样例:

在这里给出相应的输出。例如：

NULL
B

参考答案：

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main(){
    int n;
    cin>>n;
    deque<string>person;
    string op,name;
    while(n-->0){
        cin>>op;
        if(op=="q"){
            if(person.size()>0){
                cout<<person.front()<<endl;
            }
            else{
                cout<<"NULL"<<endl;
            }

        }
        else if(op=="out"){
            person.pop_front();
        }
        else{
            cin>>name;
            person.push_back(name);
        }
    }
    return 0;
}

四. 7-4 括号匹配

给定仅包含“()[]{}”六种括号的字符串，请你判断该字符串中，括号的匹配是否是合法的，也就是对应括号的数量、嵌套顺序完全正确。

输入格式:

第一行一个整数T（T<=10）

其后T行每行一个字符串只包含[{()}]六种字符（字符串长度2e5以内）

输出格式:

对于每个字符串，匹配输出Yes,否则输出No

输入样例:

2
{()[]}
([)]

输出样例:

Yes
No

参考答案：

#include<iostream>
#include<stack>
using namespace std;
int main(){
    stack<char>st;
    int n;
    cin>>n;
    string s;
    while(n-->0){
        cin>>s;
        bool flag = false;
        for(auto &c:s){
            if(c=='{'||c=='['||c=='('){
                st.push(c);
            }
            else if(c=='}'){
                if(st.empty()||st.top()!='{'){
                    cout<<"No"<<endl;
                    flag = true;
                    break;
                }
                if(!st.empty())st.pop();

            }
             else if(c==']'){
                if(st.empty()||st.top()!='['){
                    cout<<"No"<<endl;
                    flag = true;
                    break;
                }
                if(!st.empty())st.pop();
            }
             else if(c==')'){
                if(st.empty()||st.top()!='('){
                    cout<<"No"<<endl;
                    flag = true;
                    break;
                }
                 if(!st.empty())st.pop();
            }
        }
            if(!flag&&st.size()>0){
            cout<<"No"<<endl;
            }
            else if(!flag){
                cout<<"Yes"<<endl;
            }
       while(!st.empty()){
           st.pop();
       }
    }
    return 0;
}

五. 7-5 找出不是两个数组共有的元素

给定两个整型数组，本题要求找出不是两者共有的元素。

输入格式:

输入分别在两行中给出两个整型数组，每行先给出正整数N（≤20），随后是N个整数，其间以空格分隔。

输出格式:

在一行中按照数字给出的顺序输出不是两数组共有的元素，数字间以空格分隔，但行末不得有多余的空格。题目保证至少存在一个这样的数字。同一数字不重复输出。

输入样例:

10 3 -5 2 8 0 3 5 -15 9 100
11 6 4 8 2 6 -5 9 0 100 8 1

输出样例:

3 5 -15 6 4 1

参考答案：

#include<iostream>
#include<unordered_map>
#include<deque>
using namespace std;
int main(){
    int n1,n2;
    unordered_map<int,int>imap;
    deque<int>row2;
    cin>>n1;
    int num;
    while(n1-->0){
        cin>>num;
        imap[num] = 1;
    }
    cin>>n2;
    while(n2-->0){
        cin>>num;
        if(imap.count(num)){
            imap[num] = 0;
        }
        else{
            if(find(row2.begin(),row2.end(),num)==row2.end()){
                row2.push_back(num);
            }
        }
    }
    for(const auto& pair:imap){
        if(pair.second==1){
             if(find(row2.begin(),row2.end(),pair.first)==row2.end()){
           row2.push_front(pair.first);
             }
        }
    }
    bool head = true;
    for(auto& c:row2){
        if(head){
            cout<<c;
            head = false;
        }
        else{
            cout<<" "<<c;
        }
    }
    return 0;
}

pta实验五