头像

辞声


访客:1069

离线:3天前


问题 替换选择

辞声
7天前

题目链接
2020年7月第4题 PAT甲级

题目描述

当输入太大而无法放入内存时,我们必须进行外部排序而不是内部排序。外部排序的关键步骤之一是用有限的内部内存生成一组已排序的记录(也称为运行)。最简单的方法是将尽可能多的记录读入内存,并在内部对它们进行排序,然后将生成的运行结果写回某个磁带。每次运行的大小与内存的容量相同。

替代选择排序算法在1965年由donaldknuth描述。请注意,一旦第一条记录被写入输出磁带,它所使用的内存就可以用于另一条记录。假设我们按升序排序,如果下一条记录不小于我们刚刚输出的记录,那么它就可以包含在运行中。

例如,假设我们有一组输入{81,94,11,96,12,99,35},而我们的内存只能排序3条记录。用最简单的方法,我们将得到三次运行:{11,81,94},{12,96,99}和{35}。根据替换选择算法,我们将读取并排序前3个记录{81、94、11},并将11作为最小记录输出。然后有一个空间可用,因此96被读入并将加入第一个运行,因为它大于11。现在我们有了{81,94,96}。81出局后,12人进入,但必须属于下一轮,因为它小于81。因此,我们有{94,96,12},其中12将保留,因为它属于下一个运行。当94是out,99是in时,因为99大于94,它必须属于第一次运行。最终我们将得到两个运行:第一个包含{11,81,94,96,99},第二个包含{12,35}。

你的工作是实现这个替换选择算法。

输入格式:

每个输入文件包含几个测试用例。第一行给出两个正整数N(≤105)和M(<N/2),它们是要排序的记录总数和内存容量。然后在下一行中给出N个数字,它们都在int的范围内。一行中的所有数字都用空格隔开。

输出格式:

对于每个测试用例,在每一行打印替换选择算法生成的运行(按升序)。一行中的所有数字必须用1个空格隔开,行首或行尾不能有多余的空格。

输入样例:

13 3
81 94 11 96 12 99 17 35 28 58 41 75 15

输出样例:

11 81 94 96 99
12 17 28 35 41 58 75
15

个人思路:

将所有数读入一个数组然后使用两个set进行处理。
s1在容量范围内读数,遍历s1中每个数,找出比它大的最小数插入到s2,同时s1中删除这个数并加入下一个数,直至循环结束输出s2后清空。

不知道逻辑哪里出了问题,求大佬指点,这段代码打印情况在最后出现了差错。

错误的代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int n,m;
vector<int> a;//记录所有数 
set<int> s1,s2;//待排序,待输出 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        a.push_back(num);
    }

    a.push_back(0x3f3f3f3f);

    for(int i=0;i<m;i++)
        s1.insert(a[i]);
    int minnum=*s1.begin();
    s2.insert(minnum);//概数放入待输出集合 
    s1.erase(minnum);//删除待排序集合该数 
    int pre=minnum;//记录上一个待输出的数 
    for(int i=m;i<n;i++){
        s1.insert(a[i]);//每次插入1个数 
        bool flag=false;//标志位用来输出并清空s2 
        for(auto it=s1.begin();it!=s1.end();it++){
            if(*it>pre){//待输出的数必须是第一个大于等于上一个数的数 
                minnum=*it;
                flag=true;//表示始终能找到,若在s1找不到比上一个数大的则应该进行下一轮 
                break;
            }
        }
        if(!flag){
            bool f=true;
            for(auto i:s2){//输出s2 
                if(f){
                    printf("%d",i);
                    f=false;                    
                }else
                    printf(" %d",i);
            }
            printf("\n");
            s2.clear();//清空s2
            minnum=*s1.begin();
        }
        s2.insert(minnum);
        s1.erase(minnum);
        pre=minnum;//更新上一个数 
    }

    if(s2.size()){
        bool f=true;
        for(auto it:s2){
            if(f){
                printf("%d",it);
                f=false;
            }   
            else    printf(" %d",it);
        }
        printf("\n");
    }
    if(s1.size()){
        bool f=true;
        for(auto it:s1){
            if(f){
                printf("%d",it);
                f=false;
            }   
            else    printf(" %d",it);
        }
        printf("\n");
    }

    return 0;
}


活动打卡代码 AcWing 1626. 链表元素分类

辞声
12天前
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;
const int N=100010;
struct node{
    int add,data,next;
}nodes[N];

int p,n,k;

int main(){
    scanf("%d%d%d",&p,&n,&k);
    for(int i=0;i<n;i++){
        int add,data,next;
        scanf("%d%d%d",&add,&data,&next);
        nodes[add].add=add;
        nodes[add].data=data;
        nodes[add].next=next;
    }

    vector<node> v,ans;
    while(p!=-1){
        v.push_back(nodes[p]);
        p=nodes[p].next;
    }

    for(int i=0;i<v.size();i++)
        if(v[i].data<0)
            ans.push_back(v[i]);
    for(int i=0;i<v.size();i++)
        if(v[i].data>=0&&v[i].data<=k)
            ans.push_back(v[i]);
    for(int i=0;i<v.size();i++)
        if(v[i].data>k)
            ans.push_back(v[i]);

    printf("%05d %d ",ans[0].add,ans[0].data);
    for(int i=1;i<ans.size();i++)
        printf("%05d\n%05d %d ",ans[i].add,ans[i].add,ans[i].data);
    printf("-1\n"); 

    return 0;
}



辞声
13天前
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
const int N=100010;
struct node{
    int add,key,next;
}nodes[N];
int p,n;
bool vis[N];//记录所有key值绝对值是否出现过 
vector<node> ans1,ans2;

int main(){
    scanf("%d%d",&p,&n);
    for(int i=0;i<n;i++){
        int add,key,next;
        scanf("%d%d%d",&add,&key,&next);
        nodes[add].add=add;
        nodes[add].key=key;
        nodes[add].next=next;
    }

    while(p!=-1){
        if(vis[abs(nodes[p].key)]==false){
            ans1.push_back(nodes[p]);
            vis[abs(nodes[p].key)]=true;        
        }else
            ans2.push_back(nodes[p]);
        p=nodes[p].next;
    }

    printf("%05d %d ",ans1[0].add,ans1[0].key);
    for(int i=1;i<ans1.size();i++)
        printf("%05d\n%05d %d ",ans1[i].add,ans1[i].add,ans1[i].key);
    printf("-1\n");
    if(ans2.size()){
        printf("%05d %d ",ans2[0].add,ans2[0].key);
        for(int i=1;i<ans2.size();i++)
            printf("%05d\n%05d %d ",ans2[i].add,ans2[i].add,ans2[i].key);
        printf("-1\n");     
    }

    return 0;
} 


活动打卡代码 AcWing 1560. 反转链表

辞声
13天前
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;
const int N =100010;
struct node{
    int add;
    int next;
    int data;
}nodes[N];

int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin);
    #endif

    int p,n,m;
    scanf("%d%d%d",&p,&n,&m);
    for(int i=0;i<n;i++){
        int add;
        scanf("%d",&add);
        scanf("%d%d",&nodes[add].data,&nodes[add].next);
        nodes[add].add=add;
    }

    vector<node> v;
    for(int i=p;i!=-1;i=nodes[i].next)
        v.push_back({i,nodes[i].next,nodes[i].data});

    int len=v.size();
    if(v.size()%m!=0)
        len-=v.size()%m;
    for(int i=0;i<len;i+=m)
        reverse(v.begin()+i,v.begin()+i+m);

    printf("%05d %d ",v[0].add,v[0].data);
    for(int i=1;i<v.size();i++)
        printf("%05d\n%05d %d ",v[i].add,v[i].add,v[i].data);
    printf("-1\n");

    return 0;
}


活动打卡代码 AcWing 1516. 共享

辞声
13天前
#include<iostream>
#include<cstring>

using namespace std;
const int N =100010;
struct node{
    int next;
    char data;
    bool flag=false;//有无效结点 
}nodes[N];

int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin);
    #endif

    int p1,p2,n;
    scanf("%d%d%d",&p1,&p2,&n);
    for(int i=0;i<n;i++){
        int add;
        scanf("%d",&add);
        scanf(" %c %d",&nodes[add].data,&nodes[add].next);
    }

    int p=-1;//共同开始的下标 
    for(int i=p1;i!=-1;i=nodes[i].next)
        nodes[i].flag=true;
    for(int i=p2;i!=-1;i=nodes[i].next)
        if(nodes[i].flag){
            p=i;    
            break;
        }

    if(p!=-1)   printf("%05d\n",p);
    else    printf("-1\n");

    return 0;
}


活动打卡代码 AcWing 1581. 急性中风

辞声
13天前
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
const int M=1286,N=128,L=60;
int g[L][M][N];//标记是否出现过
int m,n,l,T;

struct node{//记录坐标
    int x,y,z;
};

int d[][3]={//6个方向坐标偏移量
    {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}
};

int bfs(int x,int y,int z){
    queue<node> q;
    q.push({x,y,z});
    g[x][y][z]=0;
    int cnt=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        for(int i=0;i<6;i++){//相连通的上下左右前后6个区域
            int a=t.x+d[i][0],b=t.y+d[i][1],c=t.z+d[i][2];
            if(a>=0&&a<l&&b>=0&&b<m&&c>=0&&c<n&&g[a][b][c]){
                g[a][b][c]=0;
                q.push({a,b,c});
                cnt++;
            }
        }
    }
    return cnt;
}

int main(){
    scanf("%d%d%d%d",&m,&n,&l,&T);
    for(int i=0;i<l;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<n;k++)
                scanf("%d",&g[i][j][k]);

    int res=0;
    for(int i=0;i<l;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<n;k++)
                if(g[i][j][k]){
                    int t=bfs(i,j,k);
                    if(t>=T)    res+=t;
                }
    printf("%d\n",res);

    return 0;
}


活动打卡代码 AcWing 1647. 解码PAT准考证

辞声
13天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>

using namespace std;
const int N=10010;
struct node{
    string str;
    int score;
}p[N];
int n,m;

bool cmp1(node a,node b){
    if(a.score!=b.score)
        return a.score>b.score;
    return a.str<b.str;
}

bool cmp2(pair<string,int> a,pair<string,int> b){
    if(a.second!=b.second)
        return a.second>b.second;
    return a.first<b.first;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>p[i].str>>p[i].score;
    for(int i=1;i<=m;i++){
        int a;
        string b;
        cin>>a>>b;
        printf("Case %d: %d %s\n",i,a,b.c_str());
        if(a==1){
            vector<node> ans;
            for(int j=0;j<n;j++){
                if(p[j].str[0]==b[0])   
                    ans.push_back(p[j]);
            }
            sort(ans.begin(),ans.end(),cmp1);
            if(ans.size()){
                for(auto it:ans)
                    printf("%s %d\n",it.str.c_str(),it.score);
            }else   puts("NA");
        }else if(a==2){
            int cnt=0,sum=0;
            for(int j=0;j<n;j++){
                if(p[j].str.substr(1,3)==b){
                    cnt++;
                    sum+=p[j].score;
                }   
            }
            if(cnt)
                printf("%d %d\n",cnt,sum);
            else    puts("NA");
        }else if(a==3){
            unordered_map<string,int> mp;
            for(int j=0;j<n;j++)
                if(p[j].str.substr(4,6)==b)
                    mp[p[j].str.substr(1,3)]++;
            vector<pair<string,int> > v;
            for(auto it:mp)
                v.push_back({it.first,it.second});
            sort(v.begin(),v.end(),cmp2);
            if(v.size()){
                for(auto it:v)
                    printf("%s %d\n",it.first.c_str(),it.second);
            }else
                puts("NA");
        }
    }

    return 0;
}


活动打卡代码 AcWing 1506. 中位数

辞声
13天前
#include<iostream>

using namespace std;
const int N=200010;
int a[N],b[N],c[N*2];
int n,m;

int main(){//用cin会超时
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=0;i<m;i++)
        scanf("%d",&b[i]);

    //二路归并 
    int k=0,i=0,j=0;
    while(i<n&&j<m){
        if(a[i]<=b[j])  c[k++]=a[i++];
        else    c[k++]=b[j++];
    }
    while(i<n)  c[k++]=a[i++];
    while(j<m)  c[k++]=b[j++];

    printf("%d\n",c[(n+m-1)/2]);

    return 0;
} 


活动打卡代码 AcWing 1640. 堆

辞声
13天前
#include<iostream>

//判断是否堆然后输出中序遍历
using namespace std;
const int N=1010;
int num[N];
int m,n;

void postorder(int x){//后序遍历 
    if(x*2<=n)  postorder(x*2);
    if(x*2+1<=n)    postorder(x*2+1);
    cout<<num[x];
    if(x!=1)    cout<<" ";
}

int main(){
    #ifdef  ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin);
    #endif
    cin>>m>>n;
    while(m--){
        for(int i=1;i<=n;i++)
            cin>>num[i];
        bool gh=false,lh=false;
        for(int i=1;i<=n;i++)
            for(int j=0;j<2;j++){
                if((i*2+j)<=n){
                    int a=num[i],b=num[i*2+j];
                    if(a<b) lh=true;//小根堆 
                    else    gh=true;//大根堆 
                }
            }
        if(lh&&gh)  puts("Not Heap");
        else if(lh) puts("Min Heap");
        else    puts("Max Heap");
        postorder(1);
        cout<<endl;
    }
    return 0;
} 


活动打卡代码 AcWing 1633. 外观数列

辞声
14天前
#include<iostream>
#include<cstring>

using namespace std;

int main(){
    string s;
    int n;
    cin>>s>>n;
    while(--n){//只循环n-1次
        string str;
        for(int i=0;i<s.size();){//双指针i到j之间是相同的字符,j-i为个数
            int j=i;
            while(j<s.size()&&s[i]==s[j])
                j++;
            str+=s[i]+to_string(j-i);
            i=j;
        }
        s=str;
    }
    cout<<s<<endl;
    return 0;
}