快乐模拟
算法与数据结构  0次访问

快乐模拟

😐🙂😄🤗:快乐程度依次增加。

——以下题目均来自于PAT甲级题库。

🙂1014.Waiting in Line (30分)(队列)

思路
可以发现这一题中，有一个排队的模型，这可以提示我们使用队列这个数据结构,我们用队列维护黄线内每个窗口的排队情况。注意这题在8点的时候这一天所有的人都已经排着队了，这些人中的前n*m个会排到黄线的前面，后面的在黄线后面，显然对这两波人的操作是不同的。对于前n*m个人，我们直接找到黄线前排队人数最少的窗口即可(如果该窗口不止一个就找id最小的)。而对于后面的人来说，由于此时黄线内已经排满了人，因此就得看哪个窗口最先服务完就排到哪里去，因此这里就需要比较每个队列队头元素的大小找出队头最先服务完的队列，然后排过去即可。

代码

Waiting in Line
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>

using namespace std;

const int N = 30;
int n,m,k,Q;
int fin[N];//每个窗口服务完当前队列的时间
map<int,int> res;//顾客,完成时间
queue<int> q[N];//每个队列队头的人完成的时间

int main(){
    cin>>n>>m>>k>>Q;
    for(int i=1;i<=k;i++){
        int c;
        cin>>c;
        int t=0;
        for(int j=0;j<n;j++){
            if(i<=n*m){//顾客在黄线内
                if(q[t].size()>q[j].size()) t=j;                
            }else{//顾客在黄线外
                if(q[t].front()>q[j].front()) t=j;
            }
        }
        fin[t]+=c;
        //i>n*m时黄线内已经挤满了人，从现在开始就要先出一个人然后再进一个人
        if(i>n*m) q[t].pop();
        q[t].push(fin[t]);
        //这里减c是因为五点前开始被服务的顾客可以被服务，
        //而不是五点前可以完成服务的顾客才可以被服务
        if(fin[t]-c<540) res[i]=fin[t];
    }
    
    for(int i=0;i<Q;i++){
        int c;
        cin>>c;
        if(res.count(c)) printf("%02d:%02d\n",res[c]/60+8,res[c]%60);
        else puts("Sorry");
    }
    
    return 0;
}

🙂1060 Are They Equal (25分)(字符串处理)

思路
对于这道题需要注意的是保留有效数字并不需要像数学上那样还做什么四舍五入，只是单纯的截断而已。也就是说这题核心就是要把给定的数字转换成题目中给出的表示形式。转换的步骤大致如下:
  • 找到小数点的位置k，然后去掉小数点。 (如果该数是整数没有小数点那么在最末尾加上一个小数点)
  • 由于可能存在前导0，那么每次去掉一个前导0然后k就-1。(前导0本身的存在不影响数字的大小，k是直接拿到的小数点在数字中的位置，因此这部分位置是包含了前导0的位置的，因此只有把前导0的位置去掉此时才是正确的大小)。到这一步实际上可以理解为就是把数字先转化成了"科学计数法"的形式，得到了小数部分和幂指部分。
  • 由于要求保留n位有效数字，所以我们把数字截取n位，如果数字剩下部分不足n位则要在其后补0凑足n位。这一步是在对上面的数字做截取。
  • 把答案拼凑起来。
    • 值得注意一下，上面步骤的前两步就是把一个数(整数或者小数)化成0.abc * 10 ^ k(a不等于0)形式的一个比较好的做法。

    代码

    Are They Equal
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include<iostream>
    #include<algorithm>
    #include<cstring>

    using namespace std;

    /*小数整数通用*/
    string toans(string s,int n){
        int k=s.find('.');//找到小数点的位置
        if(k==-1) s+='.',k=s.find('.');//如果数字没有小数点则在末尾加上一个小数点
        s=s.substr(0,k)+s.substr(k+1);

        //去除前导0
        while(s.size()&&s[0]=='0') s.erase(0,1),k--;//每去掉一个0就少一位
        if(!s.size()) k=0;//如果s的长度等于0，那么k=0
        //截取n位有效数字
        s=s.substr(0,n);
        //如果剩下数字不足n位要在末尾补0
        s+=string(n-s.size(),'0');
        s="0."+s+"*10^"+to_string(k);
        return s;
    }

    int main(){
        int n;
        string a,b;
        cin>>n>>a>>b;
        
        a=toans(a,n);
        b=toans(b,n);
        
        if(a==b) cout<<"YES "<<a;
        else cout<<"NO "<<a<<" "<<b;
       
        return 0;
    }

    😐1077 Kuchiguse (20分)(字符串处理)

    思路
    这一题的思路，即首先遍历后缀的长度，然后依次取所有串该长度的后缀，看看是否都相等，并找出最长的后缀。
    Kuchiguse
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include<iostream>
    #include<vector>
    #include<string>
    #include<algorithm>

    using namespace std;

    int main(){
        int n;
        vector<string> v;
        cin>>n;
        string line;
        getline(cin,line);
        while(n--){
            getline(cin,line);
            v.push_back(line);
        }
        
        //最长后缀不会超过任意一个串的长度
        //从大到小枚举最长子串的长度
        for(int k=v[0].size();k;k--){
            string t=v[0].substr(v[0].size()-k);
            bool succ=true;
            for(int i=1;i<v.size();i++){
                //长度不足k 或 后k个字符不等于t
                if(v[i].size()<k||v[i].substr(v[i].size()-k)!=t){
                    succ=false;
                    break;
                }
            }
            if(succ){
                puts(t.c_str());
                return 0;
            }
        }
        puts("nai");
        return 0;
    }

    🙂1082.Read Number in Chinese (25分)(字符串处理)

    思路
    我们可以发现每四位的读法其实是一样的，因此我们可以把数字分成3份(每四个数字为一份)，然后先正常读每一份，然后在每一份的结尾判断是否加上相应的单位("亿"，"万"，"")。 注意读的时候对"读0"有这样的规则需要准守:
  • 碰到连续的0时只读一个0。
  • 末尾不能有0出现。

    • 代码

    Read Number in Chinese
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    using namespace std;

    string maps[]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};

    //检查末尾是否是0
    bool check(string s){
        return s.size()>=5&&s.substr(s.size()-5)=="ling ";
    }

    string get(int n){
        vector<int> num;
        //注意每四位的读也有单位
        string unit[]={"","Shi ","Bai ","Qian "};//为了方便起见，没给字符串加上一段，
        //都直接在后面加上一个空格，最后直接去就好了,统一一点避免出现麻烦
        while(n) num.push_back(n%10),n/=10;
        string res="";
        for(int i=num.size()-1;i>=0;i--){
            if(num[i]) res+=maps[num[i]]+" ";
            else if(num[i]==0&&!check(res)) res+="ling ";
            if(num[i]) res+=unit[i];
        }
        //末尾不能有0
        if(check(res))
            res.erase(res.size()-5);

        return res;
    }

    int main(){
        int n;
        cin>>n;
        string res="";
        if(n<0) res+="Fu ";
        else if(n==0) res="ling ";
        n=abs(n);
        string unit[]={"","Wan","Yi"};
        vector<int> num;
        while(n) num.push_back(n%10000),n/=10000;
        //每四个数字一组
        for(int i=num.size()-1;i>=0;i--){
            if(num[i]){
                string s=get(num[i]); 
                //这里是需要加上0的情况，比如当读100800，一十万'零'八百的这个'零'就需要在这里加上
                if(num[i]<1000&&res!=""&&res!="Fu "&&!check(res)) res+="ling ";
                res+=s;
            } 
            else if(num[i]==0&&!check(res)) res+="ling ";
            if(num[i]) res+=unit[i]+" ";
        }
        
        if(res!="ling "&&check(res)) res.erase(res.size()-5);
        //把末尾的0去干净
        while(res[res.size()-1]==' ') res.pop_back();
        
        cout<<res;
        
        return 0;
    }

    😐1108.Finding Average (20分)(字符串处理)

    思路
    这一题其实不怎么快乐，主要是想尝试下try-catch语法。思路大致就是把不合法的直接输出，把合法的加起来求平均值(好吧，这就是题面的意思)。

    代码

    Finding Average
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include<iostream>

    using namespace std;

    int main(){
        int n;
        cin>>n;
        double sum=0;
        int m=0;
        while(n--){
            string s;
            cin>>s;
            bool succ=true;
            float x;
            try{
                size_t cnt;//size_t就是一个万能unsigned类型
                //转化成float类型
                x=stof(s,&cnt);//如果碰到完全不能转化的情况会直接抛出异常
                if(cnt<s.size()) succ=false;//对于3.1aaa这样的情况会截取3.1,传入cnt可以返回
                //第一个非数值字符的位置,这样就可以知道是否整个字符串都是转化为数字的
            }catch(...){//表示接受任意错误
                succ=false;
            }
            
            int k=s.find('.');
            //!!!注意一定要单独把这个证书的情况放前面单独判断!
            if(k!=-1&&s.size()-k>3) succ=false;//小数点后是否超过2位
            if(x<-1000||x>1000) succ=false;
            
            if(succ){
                m++;
                sum+=x;
            }
            else printf("ERROR: %s is not a legal number\n",s.c_str());
        }
        if(m==1) printf("The average of 1 number is %.2lf",sum/m);
        else if(m>1) printf("The average of %d numbers is %.2lf",m,sum/m);
        else if(m==0) printf("The average of 0 numbers is Undefined");
        
        
        return 0;
    }

    😄1065 A+B and C (64bit) (20分)(long long的溢出)🌌

    思路
    这里的两数相加会有两种溢出情况:
  • 如果两个负数相加得到的结果是非负数，则溢出。
  • 如果两个正数相加得到的结果是负数，则溢出。
    • 因此在判断a+b>c的时候要注意考虑如上的两种情况，第一种是"无穷小"的情况，第二种是"无穷大"的情况，剩下的就是可以正常判断的情况。 当然这题并不是到这里就完了的，因为还有着几处奇奇怪怪的坑等着去踩💢💢💢❌❌❌具体见下面代码。

    代码

    A+B and C (64bit)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include<iostream>
    using namespace std;

    typedef long long LL;

    bool check(LL a,LL b,LL c){
        LL d = a+b;//注意这里需要用一个d来接一下，否则就无法通过，总之很迷这里
        if(a>0&&b>0&&d<0) return true;
        if(a<0&&b<0&&d>=0) return false;
        return a+b>c;
    }

    int main(){
        int T;
        cin>>T;
        for(int i=1;i<=T;i++){
            LL a,b,c;
            //cin>>a>>b>>c;注意这里不要用cin来读否则有个点过不了
            scanf("%lld%lld%lld",&a,&b,&c);
            if(check(a,b,c)) printf("Case #%d: true\n",i);
            else printf("Case #%d: false\n",i);
        }
        
        return 0;
    }

    😄1095.Cars on Campus (30分)(排序+hash)🌌

    思路
    对于这道题大致的模拟过程是这样的:
    1. 首先过滤掉不合法的数据；
    2. 接着由于把时间转换成秒之后数据范围并不大，因此可以用hash来处理每个时刻停了多少辆车这个问题，我们只用先根据题意，每个时刻如果有车进那么该时刻的车辆数+1,如果车出则-1，然后再对整个时刻的数组做个前缀和，就可以得到每个时刻有多少量车了；
    3. 接着再遍历两遍数组，求出最大停车时长(注意可能多次停车,反正只要是合法的一对记录都要算上)并且求出最大停车时长的车辆。
    像这样需要求取合法的相邻时间对的题目已经碰到过几次了，在此总结一下如何优雅的求取合法的相邻时间对。
    把A(如该题的A就是某个车牌号)相关的所有时间都存到一个数组中，然后将该数组从小到大排序，然后依次遍历数组找出那些连续的in,out对。(是否需要删除那些不合法的数据要看情况，有时可能没必要，当然这更取决于自己的实现方式了。)

    代码

    Cars on Campus
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<string>

    using namespace std;

    #define fi first
    #define se second

    struct Park{
        int t;
        bool st;
        
        bool operator < (const Park &p1) const
        {
            return t<p1.t;
        }
        
    };
    map<string,vector<Park>>maps;//初始时的记录数

    int get(vector<Park> &v){
        int res=0;
        //注意这里的停车时长是指的一辆车在这一天所有的合法停车时间段之和；
        //注意一辆车可能多次的停车离开又回来
        for(int i=0;i<v.size();i+=2)
            res+=v[i+1].t-v[i].t;
        return res;

    }

    const int N=1e5+10;
    //对所有的时间做一个hash
    int num[N];
    int main(){
        int n,k;
        /*输入*/
        cin>>n>>k;
        while(n--){
            string id,t,st;
            cin>>id;
            int hh,mm,ss;
            scanf("%d:%d:%d",&hh,&mm,&ss);
            cin>>st;
            maps[id].push_back({hh*3600+mm*60+ss,st[0]=='i'?1:0});
        }
        
        /*过滤掉不合法的记录*/
        vector<Park> item;
        //！！！注意注意这里一定要加&，否则后面的v删除掉了元素，但是maps里面并没有得到修改
        for(auto& tmp:maps){
            auto& v = tmp.se;
            sort(v.begin(),v.end());
            int k=0;
            for(int i=0;i<v.size();i++){
                if(v[i].st){
                    if(i+1<v.size()&&v[i+1].st==0){
                        v[k++]=v[i];
                        v[k++]=v[i+1];
                        i++;
                    }
                }
            }
            v.erase(v.begin()+k,v.end());//删掉不合法的，后面统计最大数要用
            for(int i=0;i<k;i++) item.push_back(v[i]);
            
        }
        
        vector<string> res;
        int maxv=0;
        
        /*对每个时刻的停车数做预处理*/
        for(int i=0;i<item.size();i+=2){
            num[item[i].t]++;num[item[i+1].t]--;
        }
        for(int i=1;i<N;i++){
            num[i]+=num[i-1];
        }
    		
        /*两次循环求出停车时间最长的车及时间*/
        for(auto tmp:maps){
            maxv=max(maxv,get(tmp.se));
        }
        for(auto tmp:maps){
            if(get(tmp.se)==maxv) res.push_back({tmp.fi});
        }
        sort(res.begin(),res.end());
        
        
        /*处理询问*/
        while(k--){
            int hh,mm,ss;
            scanf("%d:%d:%d",&hh,&mm,&ss);
            int t=hh*3600+mm*60+ss;
            cout<<num[t]<<endl;
        }
        
        /*输出*/
        cout<<res[0];
        for(int i=1;i<res.size();i++) cout<<" "<<res[i];
        printf(" %02d:%02d:%02d",maxv/3600,maxv%3600/60,maxv%60);
        return 0;
    }

    🙂1105.Spiral Matrix (25分)(图形打印)🌌

    思路
    对于选出相差最少的m,n这个要求，我们直接暴力做就好了，枚举到√n,找出可以除尽的最大的一个c(列数)，然后用n/c得到r(行数)。 更值得一提的是如何填写这个螺旋矩阵，这是一个十分经典的问题。
  • 首先定义分别定义两个数组dx,dy来表示沿着上下左右移动的偏移量。
  • 由于此题是顺时针方向，所以初始时是向右的方向。
  • 当选定一个方向之后，不断的朝着这个方向走，边走边填写数字，当撞到墙之后(走出最外层边界，或者走到之前走过的位置。)，换个方向再继续走下去。

    • 代码

    Spiral Matrix
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<cmath>

    using namespace std;

    int main(){
        int n;
        //输入
        cin>>n;
        vector<int> a;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            a.push_back(x);
        }
        //greater<int>():从大到小排序
        sort(a.begin(),a.end(),greater<int>());
        
        
        //确定r,c的值
        int r=1,c=1;
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                c=i;
                r=n/i;
            }
        }
        
        //填写循环矩阵
        vector<vector<int> > v(r,vector<int>(c,0));
        //上下左右偏移量
        int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
        int k=0,dir=0;
        int i=0,j=0;
        int x=dx[dir],y=dy[dir];
        while(k<n){
            while(true){
                v[i][j]=a[k++];
                i+=x;j+=y;
                //当走到最外围边界，或者曾经走到过的结点时，要进行转向！
                if(i>=r||i<0||j>=c||j<0||v[i][j]){
                    /*当撞上墙的时候，要往回退一格再做一格，注意一定要走一格！否则会覆盖掉原来的值*/
                    i-=x;j-=y;
                    dir=(dir+1)%4;
                    x=dx[dir],y=dy[dir];
                    i+=x;j+=y;
                    break;
                }
            }
        }
        
        //输出
        for(int i=0;i<r;i++){
            cout<<v[i][0];
            for(int j=1;j<c;j++) cout<<" "<<v[i][j];
            puts("");
        }
        
        return 0;
    }

    😐1109.Group Photo (25分)🌌

    思路
    这道题，思路就是首先把整个数组按身高从高到低排序，相同身高的按字典序排序；这样排序之后数组中高的人排在前面，由于我们要先输出后排再输出前排，所以在遍历每列的时候第一列应该是倒数第1排，然后是倒数第2，倒数第3。。。 然后对于如何把人一左一右的放到一排中，这也是一个值得记忆的问题:
  • 思路比较直接，用两个指针分别指向左部和右部，只要两根指针没有超过范围就向指定的位置排人。

    • 代码

    Group Photo
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;

    const int N = 1e4+10;

    struct Person{
        string name;
        int h;
        bool operator < (const Person &p1) const{
            if(h!=p1.h) return h>p1.h;
            return name<p1.name;
        }
    }peo[N];

    string res[N];

    int main(){
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)cin>>peo[i].name>>peo[i].h;
        sort(peo,peo+n);
        int idx=0;
        //此时队列的顺序是从大往小排列的，且如果身高相同则字母序小的在前;
        //i=0时是最后一排，然后随着i的增大走后往前排
        for(int i=0;i<k;i++){
            int len=n/k;
            if(!i) len+=n%k;//特判最后一行
            //这里的len/2+1应该指的是第len/2+1的位置，所以请从编号1开始排人
            for(int r=len/2+1,l=r-1;r<=len||l>0;l--,r++){
                if(r<=len) 
                    res[r]=peo[idx++].name;//高的人排在"你"的右手边，所以管理右手边的数组在前;
                if(l>0) 
                    res[l]=peo[idx++].name;
            }
            cout<<res[1];
            for(int i=2;i<=len;i++) cout<<" "<<res[i];
            puts("");
        }
        
        return 0;
    }

    😐1051.Pop Sequence (25分)(栈)

    思路
    这道题，不用费劲心思去思考什么特别复杂的规律什么的，题目已经给出了出栈的顺序，因此我们只用模拟这个过程即可。从1到n不断的入栈元素，当栈顶元素和题目给定的序列的元素相等时，此时则出栈；如果当模拟到无法继续模拟的时候就代表序列不合法:1)超出了栈的容量;2)到最后序列没有模拟完。

    代码

    Pop Sequence
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include<iostream>
    #include<algorithm>
    #include<stack>
    using namespace std;

    int m,n,k;
    const int N = 1010;
    int a[N];
    int main(){
        scanf("%d%d%d",&m,&n,&k);
        
        while(k--){
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            stack<int> s;
            bool suc=true;
            int j=1;
            
            for(int i=1;i<=n;i++){
                s.push(i);
                //当存入的元素超过承载的容量时
                if(s.size()>m) suc=false;
                
                while(j<=n&&s.size()&&s.top()==a[j]){
                    s.pop();
                    j++;
                }
            }
            
            if(j<n) suc=false;//没有模拟完序列
            if(!suc) puts("NO");
            else puts("YES");
        }
        return 0;
    }

    🙂1055.The World’s Richest (25分)(k路归并)

    思路
    对于这道题目，我们可以分别存储各个年龄的富翁,把相同年龄的保存在一个链表中(这里用数组模拟就好)，然后再分别对每个年龄的富翁按照按worth降序，name升序的规则进行排序。由于这里的年龄最多只有200数值不大【这其实是一个k路归并的问题，本应该用堆来做，但是这里直接暴力遍历也可以过】，因此在处理每次询问的时候，只用依次遍历[amin,amax]年龄区间，比较每个年龄链表头的worth，然后找出worth最大的那个链表头输出，然后删掉该链表头(下面给每个链表开了一个idx数组用来记录遍历到链表的哪个位置了)。

    代码

    The World's Richest
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<cstring>
    #include<string>
    using namespace std;

    const int N = 210;

    struct Rich{
        string name;
        int age;
        int worth;
        
        bool operator<(Rich &r1)const
        {//这里反正是对年龄相同的一组进行排序，不需要对年龄排序了
            if(worth!=r1.worth) return worth > r1.worth;
            return name < r1.name;
        }
    };

    vector<Rich> ages[N];
    int idx[N];//记录当前年龄段的队头元素是谁

    int main(){
        int n,k;
        scanf("%d%d",&n,&k);
        char name[10];
        for(int i=0;i<n;i++){
            int age,worth;
            scanf("%s%d%d",name,&age,&worth);
            ages[age].push_back({name,age,worth});
        }
        //注意这里加&
        for(auto &v:ages) sort(v.begin(),v.end());
        
        for(int i=1;i<=k;i++){
            printf("Case #%d:\n",i);
            memset(idx,0,sizeof idx);//每次恢复队头到初始位置
            int m,amin,amax;
            scanf("%d%d%d",&m,&amin,&amax);
            bool exist = false;//是否有符合条件的人
            
            while(m--){
                int t=-1;//标记最有钱的年龄
                for(int i=amin;i<=amax;i++){//遍历年龄段
                    //注意这里相当于是用一个指针来模拟当前年龄中队头的位置
                    if(idx[i]<ages[i].size()&&(t==-1||ages[t][idx[t]].worth<ages[i][idx[i]].worth)) 
                        t = i;
                }
                if(t!=-1){//t!=-1代表找到了符合条件的人
                    Rich p = ages[t][idx[t]];
                    printf("%s %d %d\n",p.name.c_str(),p.age,p.worth);
                    idx[t]++;
                    exist = true;
                }
            }
            
            if(!exist) puts("None");
        }
        
        return 0;
    }

    🙂1057.Stack (30分)(栈+堆)🌌

    思路

    这题比较困难的地方是需要动态输出中位数，针对这个需求，我们可以把数据分为上下两部分，上部分是一个小根堆保存 \(\frac {N} {2}\)个数据；下方是一个大根堆，如果N为偶数，那么保存\(\frac {N} {2}\)，如果N是奇数那么保存\(\frac {N} {2} + 1\)个数据。这样我们只需要维护好这两个数据结构，在输出中位数的时候，直接输出下方的大根堆堆顶元素即可。

    维护堆
    如果上部分数据比下部分数据多，那么就删除上方最小的数然后拿到下面来；如果下部分比上部分的个数+1多，那么就删除下方最大的元素，拿到上面去；由于是平衡二叉树，所以每删除和插入一个元素的时间复杂度为\( O(logn)\)。

    由于c++的堆没有提供删除操作，所以对于这题，我们可以使用multiset这个数据结构，其内部实现也是平衡树，如果使用迭代器遍历输出的话，默认从小到大输出。

    代码

    Stack
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include<iostream>
    #include<algorithm>
    #include<set>
    #include<stack>
    #include<cstring>

    using namespace std;

    stack<int> s;
    multiset<int> up,down;//默认从小到大排序;其内部实现是平衡二叉树，插入和删除的时间复杂度是O(logn)

    void adjust(){
        while(up.size()>down.size()){//如果上面部分大于下面部分了
            down.insert(*up.begin());
            up.erase(up.begin());
        }
        
        while(down.size()>up.size()+1){//如果下面的部分多了
            auto k = down.end();
            k--;//注意end()-1才是最后一个元素
            up.insert(*k);
            down.erase(k);
        }
    }

    int main(){
        int n;
        cin>>n;
        char op[20] ;
        while(n--){
            scanf("%s",op);
            if(strcmp(op,"Push")==0){
                int x;
                scanf("%d",&x);
                s.push(x);
                //注意这里不能写down.empty();这样up会因为没有元素而访问了begin而报错
                if(up.empty()|| *up.begin()>x) down.insert(x);
                else up.insert(x);
                adjust();
            }else if(strcmp(op,"Pop")==0){
                if(s.empty()) puts("Invalid");
                else{
                    int x = s.top();
                    s.pop();
                    auto t=down.end();
                    t--;
                    if(*t<x) up.erase(up.find(x));//注意要先find了之后再删，如果直接up.erase(x),则会删掉所有的x
                    else down.erase(down.find(x));
                    printf("%d\n",x);
                    adjust();
                }
            }else{
                if(s.empty()) puts("Invalid");
                else{
                    auto t = down.end();
                    t--;
                    printf("%d\n",*t);
                }
            }
        }
        
        return 0;
    }

    😐1112.Stucked Keyboard (20分)(STL-string)

    思路
    此题的数据范围比较小，因此可以比较随性的做。首先找到一个第一次访问到的字符之后，就从这个位置开始遍历整个字符串，找出所有由这个字符构成的一段连续区间，看看里面的字符个数是否是k的倍数，如果所有区间都满足条件那么该字符的按键坏掉了。 之后就是替换部分了，遍历刚刚坏掉的字符，每次新建一个字符串p，p由k个当前遍历的字符组成，使用find方法，找出每次p出现的位置，然后再用replace方法替换掉p。

    代码

    Stucked Keyboard
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    using namespace std;

    map<char,bool> maps;

    int main(){
        int k;
        string s;
        cin>>k;
        getline(cin,s);
        getline(cin,s);
        
        string v="";
        for(int i=0;i<s.size();i++){
            if(!maps[s[i]]){
                maps[s[i]]=true;
                char c=s[i];
                int suc=true;
                int cnt=0;
                for(int l=i;l<=s.size();l++){
                    int times=0;
                    while(l<=s.size()&&s[l]==c){
                        l++;
                        times++;
                    }
                    if(times%k) suc=false;
                }
                if(suc) v+=c;
                    
            }
        }
        
        cout<<v<<endl;
        /*替换字符*/
        for(int i=0;i<v.size();i++){
            string p(k,v[i]);//(长度,'字符')
            string C(1,v[i]);//替换的时候要用字符串替换
            int pos=s.find(p);
            while(s.find(p,pos)!=string::npos){
                pos=s.find(p,pos);//注意为了防止当连续的一串字符被替换之后又重新组合成合法字符这种情况,因此你必须规定每次
                //开始寻找字符的起始位置，这样就避免会一直替换下去
                s.replace(pos,k,C);//用C替换从pos开始的k个字符
                pos++;//当前找到p的位置是pos，下一次要从pos+1开始找p
            }
        }
        
        cout<<s;
        return 0;
    }

    😐1145.Hashing - Average Search Time (25分)

    思路
    这题就是模拟一下hash表，在插入的时候把要插入的数字x对hash表的长度s取模得到idx，然后开始迭代，每次把idx加一个k(0<= k< s )的平方，看看对应的位置是否有值，没有的话就直接插入，有的话则继续迭代;如果迭代结束之后还没有找到合适的位置则不可以插入返回-1。

    对于查找操作，和上面一样，得到idx之后开始迭代，每次加一个k(0<= k< s )的平方，如果某位置的值等于当前查找数字x的值则返回，否则继续迭代，迭代结束还没有找到返回-1。

    代码

    Hashing - Average Search Time
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    #include<iostream>

    using namespace std;

    const int N = 1e4+10;
    int h[N];

    bool is_prime(int x){
        if(x==1) return false;
        for(int i=2;i*i<=x;i++)
            if(x%i==0) return false;
        return true;
    }

    int s,n,k;
    int find(int x,int &cnt){
        int idx=x%s;
        cnt=1;
        for(int i=0;i<s;i++,cnt++){
            int k=(idx+i*i)%s;
            //插入的时候如果h[k]为空则返回；查找的时候如果找到了就返回
            if(!h[k]||h[k]==x) return k;
        }    
        return -1;
    }



    int main(){
        scanf("%d%d%d",&s,&n,&k);
        while(!is_prime(s)) s++;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            int t;
            int idx=find(x,t);
            if(idx==-1) printf("%d cannot be inserted.\n",x);
            else h[idx]=x;
        }
        int cnt=0;
        for(int i=0;i<k;i++){
            int x;
            scanf("%d",&x);
            int t;
            int idx=find(x,t);
            cnt+=t;

        }
        printf("%.1lf",(double) cnt/k);
        return 0;
    }
    #

    喜欢这篇文章？打赏一下作者吧

    评论

    最新文章

    ×