【CSP CCF记录】201803-2第13次认证 碰撞的小球
题目
样例输入1
3 10 5
4 6 8
样例输出1
7 9 9
样例输入2
10 22 30
14 12 16 6 10 2 8 20 18 4
样例输出2
6 6 8 2 4 0 4 12 10 2
思路
梳理题意，本题主要考虑三种情况：
1.小球正常运动
2.小球抵达线段两段
3.两个小球在线段某位置相撞
前两种情况很好表示，对于第三种情况，我们需要解决两个问题：
- 如何知道线段该位置已经有小球？
- 如何找到线段该位置另一个小球的编号？
为了解决以上问题，我们可以设一个line[]数组，专门记录第一个抵达某线段位置的小球编号。以下模拟一次小球在线段上的运动，分析line[]的用法。
当时刻t=j时，i号小球离开原先位置，即line[a[i]]=0，抵达新位置a[i]+=v[i]。
- 若新位置已经有其他小球了，即line[a[i]]!=0，由于line[]数组记录的是小球编号，因此我们可以轻易找到之前的小球。在之后的t=j+1时刻中，任一小球离开都会执行一次line[a[i]]=0，含义为：这两个小球从该线段位置同时离开了，现在该线段位置没有小球。
- 若新位置无其他小球，则line[a[i]]=i，表示该线段位置已被第i号小球占据了。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,L,t;
int a[105]={0},v[105]={0},line[1005]={0};
cin>>n>>L>>t;
for(int i=1;i<=n;i++)
{
cin>>a[i];
v[i]=1;
line[a[i]]=i;//这个线段该位置有小球 ai
}
for(int j=1;j<=t;j++)
{
for(int i=1;i<=n;i++)
{
line[a[i]]=0;//ai从先前的线段位置离开
a[i]+=v[i];
if(a[i]==0||a[i]==L)//碰到端点
{
v[i]*=-1;
line[a[i]]=i;//ai到达该位置
}
else if(line[a[i]]!=0)//线段该位置已有小球，两球相撞
{
v[line[a[i]]]*=-1;
v[i]*=-1;
}
else
{
line[a[i]]=i;//ai到达该位置
}
//cout<<a[i]<<" ";
}
//cout<<endl;
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}结果
需要注意的是，一开始我设置了一个动态数组，导致出现运行时内存空间不足，可以先开静态数组解决。
int a[n+1]={0},v[n+1]={0},line[L+1]={0};//改进前
int a[105]={0},v[105]={0},line[1005]={0};//改进后
原文地址：https://blog.csdn.net/m0_73733846/article/details/144054202
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！