CF构造题1600-1800(1)
D. Same Count One(Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!))
题意
给定 (n) 个长度为 (m) 的 01 序列,每次操作可以选择两个序列a1
, a2
,并选择一个(pos), std::swap(a1[pos], a2[pos])
, 求是每个序列中的 (1) 的个数都相等所需的最小操作数。
思路
可以发现 ((1) 的总数 ) (mod n eq 0) 时, 是无解的。
令 (avg =) ((1) 的总数 ) (/ n), 我们可以把这 (n) 个序列分为两类,严格小于 (avg) 的 和严格大于 (avg) 的,其他的序列可以丢掉。
严格大于 (avg) 的序列都可以为 严格小于 (avg) 的序列补充 (1), 直到 严格大于 (avg) 的序列 (1) 的个数等于 (avg) 或者 严格小于 (avg) 的序列 (1) 个数等于 (avg)。
直接模拟即可。
实现
void solve_problem() {
int n, m;
std::cin >> n >> m;
std::vector a(n, std::vector<int>(m, 0));
int avg = 0;
for (int i = 0;i < n; i++) {
for (int j = 0; j < m; j++) {
std::cin >> a[i][j];
avg += a[i][j];
}
}
if (avg % n == 0) {
if (n == 1) {
std::cout << 0 << "
";
return;
}
avg /= n;
std::vector<std::pair<int,int>> q1, q2;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < m; j++) {
cnt += a[i][j];
}
if(cnt < avg) q1.push_back({cnt, i});
else if (cnt > avg) q2.push_back({cnt, i});
}
int ans1 = 0;
std::vector<std::array<int, 3>> ans2;
for (int i = 1; i <= n; i++) {
if (q1.empty() || q2.empty()) break;
auto [c1, i1] = q1[0];
auto [c2, i2] = q2[0];
int d = avg - c1;
for (int j = 0; j < m; j++) {
if (d == 0 || c2 == avg) {
break;
}
if (a[i2][j] == 1 && a[i1][j] == 0) {
std::swap(a[i2][j], a[i1][j]);
c1++;
c2--;
d--;
ans2.push_back({i2 + 1, i1 + 1, j + 1});
ans1++;
}
}
q1[0] = {c1, i1};
q2[0] = {c2, i2};
if (c1 == avg) q1.erase(q1.begin());
if (c2 == avg) q2.erase(q2.begin());
}
std::cout << ans1 << "
";
for (auto [x, y, z] : ans2) {
std::cout << std::max(x, y) << " " << std::min(y, x) << " " << z << "
";
}
} else {
std::cout << -1 << "
";
}
}
D. Watch the Videos(2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams))
题意
有 (n) 个大小随意的视频和 (1) 个大小为 (m) 的磁盘,视频要下载到磁盘中才可以开始观看,下载第 (i) 个视频花费 (a_i) 的时间,开始下载第(i)个视频时,磁盘中要至少有(a_i)的空间才可以开始,下载完成需要花费 (1) 的时间观看完,看完之后视频立刻被从磁盘中删除,求看完所有视频需要的时间。(一次只能下载一个视频,观看视频的时候可以开始下载视频)
思路
最坏的答案(每次看完一个视频后才开始下载下一个视频), 计算方法为:
可以发现如果在观看视频时下载视频,答案就可以 (-1) 。
要想使答案最小,只需要尽可能多的在观看视频时开始下载视频即可。
假设视频序列 (a) 从小到大排序, 那么可以找到一个最大的 (pos (1leq pos leq n)), 使得序列
相邻两个数的和小于等于 (m)。
按照这个序列观看,有 (pos - 1) 个视频是在正在观看视频时开始下载的。可以使答案减少 (pos - 1)。
(pos) 是满足单调性的,因此可以二分来找到最大的 (pos)。
实现
void solve_problem() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (auto &x : a) {
std::cin >> x;
}
std::sort(a.begin(), a.end());
auto check = [&](int x) {
int l = 0, r = x - 1;
while (l < r) {
if (a[r] > m - a[l]) return false;
r--;
l++;
}
return true;
};
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
std::cout << std::accumulate(a.begin(), a.end(), 0LL) + (n - ans + 1) << "
";
}
D. Range = √Sum(Codeforces Round #836 (Div. 2))
题意
构造一个长度为 (n) 的数组 (a_1,a_2, a_3, dots,a_n),使 (a_i) 各不相同,且 (max(a_1,a_2, a_3, dots,a_n) - min(a_1,a_2, a_3, dots,a_n) = sqrt{a_1,a_2, a_3, dots,a_n}) 。
思路
当 (n) 为偶数时, 数组为:
数组可以被分成 (frac{n}{2}) 组,每组的和都为 (2n)。
当 (n) 为奇数时,我们尝试 (max(a) - max(b) = n + 1), 因此数组的和应为 (n^2 + 2n + 1)。
尝试使用 (n - 1) 个数分为 (frac{n-1}{2}) 组,每组和为 (2(n+1)), 组成的数组和为 (n^2 - 1)。
此时这 (n - 1) 个数为:
知道了最小项,最大项也可以计算出来 (n + frac{n - 1}{2} + 3)。
这时数组的和为:
距离 (n^2 + 2n + 1) 还需要:
我们可以让 第 (frac{n - 1}{2} + 1) 项到第 (n - 1) 项都 (+1) 来抵消掉 (frac{n - 1}{2})。
因为第 (n - 1) 项 (n + frac{n - 1}{2} + 1) 与 第 (n) 项 (n + frac{n - 1}{2} + 3) 相差 (2),所以 (+1) 操作不会使数组产生重复的数。
此时我们的数组已经构造完成:
实现
void solve_problem() {
int n;
std::cin >> n;
if (n % 2 == 0) {
for (int i = 0; i < n/2; i++) std::cout << (n/2 + i) << " ";
for (int i = 1; i <= n/2; i++) std::cout << (n + i) << " ";
std::cout << "
";
} else {
for (int i = 1; i <= (n - 1) / 2; i++) std::cout << (n - 1) / 2 + i + 1 << " ";
for (int i = 1; i <= (n - 1) / 2; i++) std::cout << n + i + 2 << " ";
std::cout << n + (n - 1) / 2 + 3<< "
";
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十