码风丑陋,大佬勿喷
正文
C题
题目大意
给定两个长度分别为 和 的序列 和 ,合并两个序列。 最后输出原来两个序列里的每个数在新序列中的位置。
思路分析
合并序列纯模拟即可。 输出时二分查找位置。
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[100005],b[100005],c[200005];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
int i=1,j=1,p=1;
while(i<=n&&j<=m){
if(a[i]<b[j])c[p++]=a[i++];
else c[p++]=b[j++];
}
while(i<=n)c[p++]=a[i++];
while(j<=m)c[p++]=b[j++];
k=n+m;
for(int i=1;i<=n;i++)printf("%d ",lower_bound(c+1,c+k+1,a[i])-c);
printf("\n");
for(int i=1;i<=m;i++)printf("%d ",lower_bound(c+1,c+k+1,b[i])-c);
}
D题
题目大意
有 个人在银行里排队,总共发生了 件事情,有以下三种可能:
-
1 :呼叫号码最小但未被叫到的人
-
2 :已被叫到但没有来的人来了,他的编号是
-
3 :再次呼叫号码最小但已经被叫到的人
思路分析
开两个队列 和 , 记录没有被叫到的人, 记录被叫到的人。 再开一个 数组,记录哪些人被叫到了而且来了
对于 1 操作, 加入 当前最小的数, 弹出一个
对于 2 操作,用 记录 为已被叫到且来了的人
对于 3 操作,从小到大枚举 中的数,根据 数组判断当前是不是被叫到了但没有来的。如果来过了,弹掉那个数。当找到了第一个符合条件的的数时,输出这个数。
代码部分
#include<bits/stdc++.h>
using namespace std;
int n,q,o,x;
queue<int>a,b;
int f[500005];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)a.push(i);
while(q--){
scanf("%d",&o);
if(o==1)b.push(a.front()),a.pop();
else if(o==2)scanf("%d",&x),f[x]=1;
else{
while(f[b.front()]==1)b.pop();
printf("%d\n",b.front());
}
}
}
E题
题目大意
有一个两行 列的矩阵,以如下形式给定:
对于第一行,给定 个二元组( , ),表示有 个 。
对于第二行,给定 个二元组( , ),表示有 个 。
最后输出有几列同列不同行的数相等。
思路分析
直接模拟。
代码部分
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,s=0;
int x[100005],y[100005],xx[100005],yy[100005];
signed main(){
scanf("%lld%lld%lld",&t,&n,&m);
for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
for(int i=1;i<=m;i++)scanf("%lld%lld",&xx[i],&yy[i]);
int i=1,j=1;
while(i<=n&&j<=m){
int o=min(y[i],yy[j]);
if(x[i]==xx[j])s+=o;
if(y[i]==o)y[i++]=0,yy[j]-=o;
else if(yy[j]==o)yy[j++]=0,y[i]-=o;
}
printf("%lld",s);
}