内存限制: 256 Mb时间限制: 1000 ms
题目描述
有 n 名士兵参加了一场激烈的战斗。每个士兵身边有两个伙伴，第 i 号士兵的左侧伙伴编号为 i−1，右侧伙伴的编号为和 i+1。1 号士兵没有左侧伙伴，n 号士兵没有右侧伙伴。
在战斗过程中，陆续牺牲了 m 名士兵。一旦一名士兵牺牲了，存活的士兵就会相互接近，形成新的伙伴关系。给定士兵们牺牲的顺序及编号，请你输出当每个士兵牺牲时，新构成伙伴关系的两个士兵的编号。
输入格式
第一行：两个正整数表示 n 和 m。
第二行到第 m+1 行：在第 i+1 行，有一个正整数 si ，表示第 i 个牺牲的士兵编号。
输出格式
共 mm 行：每行两个整数，第 ii 行表示当 si 牺牲时，左右伙伴的编号，如果某侧没有伙伴，输出一个 *。
数据范围
对于 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
这是一道挺好的链表模拟题 对于初学链表的同学 难度不大也容易理解。
解题思路一 数组暴力模拟
建立数组模拟每一个士兵的状态，0为存活，1为牺牲，每次查找都搜索他左侧第一个存活的士兵和右侧第一个存活的士兵。
时间复杂度为平方级别。能够拿到60分。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int a[1000005]; 4. int main() 5. { 6. int n,m,t; 7. cin>>n>>m; 8. while(m--){ 9. cin>>t; 10. int i=t-1; 11. while(a[i]>=1&&a[i]!=0)i--; 12. if(i<1) cout<<"* "; 13. else cout<<i<<" "; 14. i=t+1; 15. while(a[i]<=n&&a[i]!=0)i++; 16. if(i>n) cout<<"*"<<endl; 17. else cout<<i<<endl; 18. a[t]=1; 19. } 20. return 0; 21. }
解题思路二 模拟双向链表。
根据相同的原理，我们可以给每个士兵都分配两个值：左边（前面）的士兵和右边（后面）的士兵。
当一个士兵牺牲时，更新他左边士兵的右边士兵为他的右边士兵和他右边士兵的左边士兵为他的左边士兵。
在输入时，只需根据对应的下标访问就可以了。
总体的时间复杂度降到了O(n)。能够拿到100分。
1. #include<bits/stdc++.h> 2. using namespace std; 3. struct Nod{ 4. int lf,rt; 5. }a[1000005]; 6. int main() 7. { 8. int n,m,t; 9. cin>>n>>m; 10. for(int i=1;i<=n;i++){ 11. a[i].lf=i-1; 12. a[i].rt=i+1; 13. } 14. while(m--){ 15. cin>>t; 16. if(a[t].lf==0) cout<<"* "; 17. else cout<<a[t].lf<<" "; 18. if(a[t].rt==n+1)cout<<"*"<<endl; 19. else cout<<a[t].rt<<endl; 20. a[a[t].rt].lf=a[t].lf; 21. a[a[t].lf].rt=a[t].rt; 22. } 23. return 0; 24. }
