传送门
这是我做过最简单的 。
先考虑非法的情况。显然,如果n个缺失的骰子全置为6都不能使骰子值之和满足题设条件,这组数据就找不到合法答案。同理可得,n个缺失骰子全为1都不满足题设也是一种镜像情况。这样我们就得到了这道题的边界条件。
接着考虑合法解法。我们可以根据rolls数组之和与mean值计算出n个缺失数据的平均值,将这个值向下取整,就是每个缺失骰子的“最低值”。再依次给n个骰子分配点数,直到分完为止。这样就能依次得出合法的答案序列。
class Solution {
public:
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
int m = rolls.size();
int tot = 0;
for (auto roll : rolls) tot += roll;
int idealSum = (n + m) * mean;
if (idealSum - tot > n * 6) {
return {};
} else if (idealSum - tot < n) {
return {};
}
// cout << n << endl;
double ansMean = ((idealSum * 1.0 - tot * 1.0) / n * 1.0);
// cout << ansMean << " " << (int)ansMean << endl;
if (ansMean - (int)ansMean == 0) {
vector<int> ans;
for (int i = 0; i < n; i++) {
ans.push_back(ansMean);
}
return ans;
} else {
int remainSum = idealSum - tot;
remainSum -= (int)ansMean * n;
vector<int> ans(n, (int)ansMean);
int pos = 0;
while(remainSum > 0) {
ans[pos]++;
remainSum--;
pos = (pos + 1) % n;
}
return ans;
}
}
};
评论
评论功能已经关闭!