碰撞球游戲，CCF201803-2 碰撞的小球（100分）【模擬】

?

問題鏈接：CCF201803-2 碰撞的小球

問題分析：

小球碰撞實驗視頻，? 這是一個模擬題，按照時間序列進行模擬，模擬小球的運動過程。好在每個時間單位小球只移動一個位置，處理起來就要簡單一些。模擬題關鍵在于采用什么樣的數據表示，這里給出2種解法。

? 方法一（不排序，暴力）：

? 使用數組pos[i]存儲第i個球的初始位置；使用數組step[i]存儲第i個球現在的運動方向，step[i]=1表示向右走，step[i]=-1表示往左走，用加法運算就可以實現小球的移動。

? 模擬過程是按照時間序列，先計算小球的下一個位置，如果該位置為兩端則改變運動方向。再根據小球的新位置看看有沒有2個小球碰頭，有的話分別改變運動方向。只是簡單地判斷2個小球是否碰頭需要用暴力法算一下。

小球碰撞實驗報告？? 方法二（結構數組，排序）：

? 如果不想用暴力，則將有關參數放入一個結構數組中，給每一個小球編號，排序后再進行模擬，輸出結果時再按照編號重新排序即可。

程序說明：（略）

題記：

質量相同兩個小球碰撞？? 沒有好辦法就暴力，沒有好辦法就模擬。這個題正好應驗了這兩句話。

?

提交后得100分的C++語言程序（方法一）如下：

/* CCF201803-2 碰撞的小球 */#include <iostream>using namespace std;const int L = 1000;
int pos[L + 1], step[L + 1];int main()
{int n, l, t;cin >> n >> l >> t;for(int i = 0; i < n; i++) {cin >> pos[i];// 開始往右走，到達兩端則回頭step[i] = 1;if(pos[i] == l || pos[i] == 0)step[i] = -step[i];}for(int i = 0; i < t; i++) {// 走一步for(int j = 0; j < n; j++) {pos[j] += step[j];// 到達兩端則回頭if(pos[j] == l || pos[j] == 0)step[j] = -step[j];}// 判斷是否碰頭，碰頭則掉頭（要避免重復比較）for(int j = 0; j < n; j++)for(int k = j + 1; k < n; k++)if(pos[k] == pos[j])step[k] = -step[k], step[j] = -step[j];}for(int i = 0; i < n; i++)cout << pos[i] << " ";cout << endl;return 0;
}

?

碰撞的小球、提交后得100分的C++語言程序（方法二）如下：

/* CCF201803-2 碰撞的小球 */#include <iostream>
#include <algorithm>using namespace std;const int N = 100;
struct Node {int id;         // 小球編號int pos;        // 位置int step;       // 運動方向，1表示向右，-1表示向左
} b[N];bool cmp1(Node a, Node b)
{return a.pos < b.pos;
}bool cmp2(Node a, Node b)
{return a.id < b.id;
}int main()
{int n, l, t, id = 0;cin >> n >> l >> t;for(int i = 0; i < n; i++) {b[i].id = ++id;cin >> b[i].pos;// 開始往右走，到達兩端則回頭b[i].step = 1;if(b[i].pos == l || b[i].pos == 0)b[i].step = -b[i].step;}sort(b, b + n, cmp1);for(int i = 0; i < t; i++) {// 走一步for(int j = 0; j < n; j++) {b[j].pos += b[j].step;// 到達兩端則回頭if(b[j].pos == l || b[j].pos == 0)b[j].step = -b[j].step;}// 判斷是否碰頭，碰頭則掉頭（排序后只需要比較相鄰的）for(int j = 1; j < n; j++)if(b[j].pos == b[j - 1].pos)b[j].step = -b[j].step, b[j - 1].step = -b[j - 1].step;}sort(b, b + n, cmp2);for(int i = 0; i < n; i++)cout << b[i].pos << " ";cout << endl;return 0;
}

?

?