题目链接 https://codeforces.com/contest/1372/problem/F
题面 【ACM|Codeforces Round #655 (Div. 2) F】
文章图片
题意 这个是交互题，要求的是个长度为 n n n的单调不降的序列，每次给一个询问?lr ?\ l\ r ? l r，返回的是该区间的最小众数以及其出现的次数x , f x,f x,f。
思路 由于要求的数组是单调不降的，这样可以保证[ r + 1 ? f , l ? 1 + f ] [r+1-f,l-1+f] [r+1?f,l?1+f] 区间内必定是x x x，所以可以考虑分治来不断缩小区间。
参考代码
#include
using namespace std;
#define MP(a, b) make_pair(a, b)
#define P pair
const int N = 2e5 + 10;
int ans[N];
P query(int l, int r) {
printf("? %d %d\n", l, r);
fflush(stdout);
int x, f;
scanf("%d%d", &x, &f);
return MP(x, f);
}
void solve(int l, int r) {
if (l <= r) {
P x = query(l, r);
int L = r - x.second + 1, R = l + x.second - 1;
if (L <= R) {
for (int i = L;
i <= R;
i++) {
ans[i] = x.first;
}
solve(l, L - 1);
solve(R + 1, r);
} else {
int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
}
}
return;
}
int main() {
int n;
scanf("%d", &n);
solve(1, n);
printf("! ");
for (int i = 1;
i <= n;
i++) {
printf("%d ", ans[i]);
}
puts("");
fflush(stdout);
return 0;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。