联想算法题-小朋友分糖果
问题描述
有n个小朋友围成一圈，假设他们的编号分别为1,2,…,n，编号为i与编号为i+1(1<=i<n)的小朋友互为相邻关系，特别地，编号为1与编号为n的小朋友也互为相邻关系。
每个小朋友都带了一些糖果[a_1,a_2,…,a_n]，a_i表示第i个小朋友带的糖果数量。现在老师带着他们做一个这样的游戏：每当老师喊“交换”时，所有的小朋友都会将自己当前手上的糖果分给相邻的小朋友：如果手上糖果的数量是偶数，则平分给左右两个相邻的小朋友；如果手上糖果的数量是奇数，那么自己留下1个糖果，再将剩下的糖果评分给左右两个相邻的小朋友。
在老师喊了k次“交换”后，每个小朋友需要报告自己手上的糖果数量。
例如当n=4且k=3时，假设一开始小朋友带的糖果数量为[2,3,5,4]，那么进行3次“交换”后糖果数量情况为：[2,3,5,4]=>[3,4,4,3]=>[4,3,3,4]=>[3,4,4,3]。
0 4 5 5
2 0 7 5
2 3 1 8
6 3 5 0
输入描述
第一行两个正整数n和k，分别表示小朋友的数量和要进行“交换”的次数。
第二行n个整数a_1,a_2,…,a_n，其中a_i表示编号为i的小朋友带的糖果数量。
输出描述
一行n个用空格隔开的数b_1,b_2,…b_n，其中b_i表示编号为i的小朋友最终手上的糖果数量。
输入样例1
4 3
2 3 5 4
输出样例1
3 4 4 3
样例解释1
如题面描述中所示。
数据范围和说明
30%的数据保证：3<=n<=10, 1<=k<=100, 0<=a_i<=100
80%的数据保证：3<=n<=100, 1<=k<=100, 0<=a_i<=100
100%的数据保证 ：3<=n<=500, 1<=k<=1000, 0<=a_i<=100
算法思路：
这个算法思路是模拟，但是重点在于，一定要创建新的数据，如果直接在原数组基础上进行操作，会出现
问题，原因是他们是同时操作的，而不是从第一个开始到最后一个，如果是从第一个到最后一个这样的顺序，那么就是第二种写法。
#include <iostream> #include <vector> using namespace std; vector<int> candy_game(int n, vector<int>& candies, int k) { for (int t = 0; t < k; ++t) { vector<int> new_candies(n, 0); // 用于存储每次交换后的糖果数量 for (int i = 0; i < n; ++i) { if (candies[i] % 2 == 0) { // 如果糖果数量为偶数，平分给左右两个相邻的小朋友 new_candies[(i + n - 1) % n] += candies[i] / 2; new_candies[(i + 1) % n] += candies[i] / 2; } else { // 如果糖果数量为奇数，保留1个，再平分给左右两个相邻的小朋友 new_candies[(i + n - 1) % n] += candies[i] / 2; new_candies[i] += 1; new_candies[(i + 1) % n] += candies[i] / 2; } } candies = new_candies; } return candies; } int main() { int n, k; cin >> n >> k; vector<int> candies(n); for (int i = 0; i < n; ++i) { cin >> candies[i]; } // 输出最终糖果数量 vector<int> result = candy_game(n, candies, k); for (int i = 0; i < n; ++i) { cout << result[i] << " "; } return 0; }
非同时的情况的代码写法
#include<iostream> #include<vector> using namespace std; int main() { int n, k; vector<int> q; cin >> n >> k; for (int i = 0; i < n; ++ i) { int t; cin >> t; q.push_back(t); } while(k --) { for (int i = 0; i < n; ++ i) { int t = q[i] / 2; if (q[i] % 2 == 0) q[i] = 0; else q[i] = 1; q[(i + n - 1) % n] += t; q[(i + 1) % n] += t; } } for (int i = 0; i < n; ++ i) cout << q[i] << " "; return 0; }
4 3 2 3 5 4
运行结果
6 4 3 1
