上海计算机学会2020年4月月赛C++乙组T1伙伴
发布时间
阅读量：
阅读量
题目描述
共有 n 位战士参与了一场激烈的战斗。每位战士身边都配两名伙伴 ，其中第 i 位战士的左边伙伴编号为 i−1 ，右边伙伴的编号则为 i+1 。值得注意的是，在第 11 位战士的位置上并不存在左边伙伴 ，而在第 n 位战士的位置上则不存在右边伙伴 。
在战斗中进行时,陆续有m名战士倒下.每当一名战士倒下后,留下的战士彼此靠近,从而形成了新的…关系.若给出所有战俘被俘顺序及其编号,请计算每个战士倒下后所形成的新的…关系的具体情况.
输入格式
第一行：由两个正整数组成n和m。
第二行到第m+1行：在第i个牺牲的士兵的编号为si。
输出格式
共有m组数据：每一组数据包含两个整数值。每当si被牺牲时，请输出左右两侧的伙伴编号；若某一侧无 partners，则以星号*替代。
数据范围
- 对于 30% 的数据，1≤n≤10000；
- 对于 60% 的数据，1≤n≤100000；
- 对于 100% 的数据，1≤n≤1000000，1≤m<n。
样例数据
输入如下所示：
5→3
接着单独列出：
3
然后列出：
2
最后给出：
1
输出结果如下所示：
2→4
接着单独列出：
1→4
最后给出：
*→4
解析：该程序通过模仿双向链表的方式存储数据，
其中键值对表示为键←→值的形式，
完整代码可参考链接
#include <iostream>
#include <algorithm>
using namespace std;
int R[1000005],L[1000005];
int main()
{
int n,m,s;
cin>>n>>m;
for (int i=1;i<=n;i++){
L[i]=i-1;//左手边伙伴是上一个编号
R[i]=i+1;//右手边伙伴是下一个编号
}
for (int i=1;i<=m;i++){
scanf("%d",&s);
if (L[s]==0){//左手边伙伴没有
printf("* %d\n",R[s]);
}else if (R[s]==n+1){//右手边伙伴没有
printf("%d *\n",L[s]);
}else{//左右手边都有
printf("%d %d\n",L[s],R[s]);
}
R[L[s]]=R[s];//左手边伙伴的右手换成右手边伙伴
L[R[s]]=L[s];//右手边伙伴的左手换成左手边伙伴
}
return 0;
}全部评论 (0)
还没有任何评论哟~