题目1
给你一个数组 对于其中的奇数 你可以让他*＝ 2 对于其中的偶数 你可以让他 /= 2 记这个数组最大值与最小值之差为 偏移量 返回偏移量的最小值
思路： 对于所有的奇数 我们可以先
*＝ 2让它获得被除的机会 接下来 我们只需要用multiset 维护这个数组 然后不断对最大值除以二 并记录偏移量即可
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
multiset<int> mst;
for (int i = 0; i < n; i++)
{
if (v[i] & 1) v[i] *= 2;
mst.insert(v[i]);
}
int ans = *mst.rbebin() - *mst.begin();
while (*mst.rbegin() % 2 == 0)
{
auto num = *mst.rbegin();
mst.erase(num);
num /= 2;
mst.insert(num);
ans = min(ans, *mst.rbebin() - *mst.begin());
}
cout << ans;题目2
森林中有很多只兔子 你问了一些兔子”有几只兔子跟你颜色相同？” 兔子们的回答绝对真实 但是你可能只问了一部分兔子 现在你得到了兔子们的回答answer 求森林中至少有多少只兔子
思路： 对于所有回答一样的兔子，对他们分组 每n + 1 只兔子分为一组，最后乘n + 1 就得到了答案
代码：
int n;
cin >> n;
map<int, int> mp;
while (n--)
{
int num;
cin >> num;
mp[num]++;
}
int ans = 0;
for (auto &&[k, v] : mp)
{
// 每n + 1只分为一组 也就是总数 / n + 1 向上取整
auto a = (v + (k + 1) - 1) / (k + 1);
ans += a * (k + 1);
}
cout << ans;总结： 向上取整的操作通常应用于对某个目标分组，比如 现在有七十个学生，每辆车最多可以垃50个 请问一共需要用几辆车 这种时候分组策略就是总数 / 分组依据 然后向上取整 也就是ans = (a + b - 1) / b
题目3
给定两个数组nums和target 你可以对nums的任意两个元素作变换（其中一个+= 2 另外一个-= 2 返回你要操作多少次才能使得这两个数组相等 （可以证明一定存在相等策略
思路：这道题的简化背景其实是 给两个数组 可以对其中一个的任意元素增减 返回使得这两个数组元素相等的最小操作次数 对两个数组都排序，就显而易见的得出答案了
那么对于这一题 我们需要注意到，每次增加减少2 不会改变他们的奇偶性——所以我们应该对奇偶性分组 分组之后 我们直接记录变换次数然后除以二即可
int n;
cin >> n;
vector<int> v(n), t(n);
for (int i = 0; i < n; i++) cin >> v[i];
for (int i = 0; i < n; i++) cin >> t[i];
auto change = [&](vector<int> &v) -> void
{
vector<int> odd, even;
for (int i = 0; i < n; i++)
{
if (v[i] & 1)
{
odd.emplace_back(v[i]);
}
else
{
even.emplace_back(v[i]);
}
}
ranges::sort(odd);
ranges::sort(even);
odd.insert(odd.end(), all(even));
v = odd;
};
change(v);
change(t);
int ans = 0;
for (int i = 0; i < n; i++) ans += abs(v[i] - t[i]) / 2;
cout << ans / 2;总结： 下次遇到增减2的时候 要注意这不会改变奇偶性
题目4
部门要挑选两个员工去参加竞赛，每一个员工有a b 两个指标 部门会把两个员工的两个指标分别取平均值得到A B 求min(A,B)的最大值
思路： 的思路是容易想到的，但是我们不允许这样的复杂度 在此基础上 我们应当保证尽可能取消内层循环 我们应当使用 来sort 这样一来 我们有： 对于任意
v[i](abs(a - b) == k) 它前面的所有a和b一定满足abs(a - b) ⇐ k 也就是说 相加之后不会改变min所在的位置 因此 我们直接设置两个变量记录最大值最小值即可
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
ranges::sort(v, [](auto a, auto b) {
return abs(a.first - a.second < b.first - b.second;) });
int max1 = a.first, max2 = a.second, ans = 0;
for (int i = 1; i < n; i++)
{
ans = min(v[i].first + max1, v[i].second + max2);
max1 = max(max1, v[i].first);
max2 = max(max2, v[i].second);
}
cout << ans * 0.1 / 2;