#P1973. 第3题-小明和小美
-
1000ms
Tried: 115
Accepted: 9
Difficulty: 7
所属公司 :
美团
时间 :2024年8月31日
第3题-小明和小美
思路:单调栈+ST表/线段树
显然,对于先手仅能选取[l,r]中最大的数,因此我们需要知道该区间的最大值,可以用ST表/线段树等数据结构进行预处理,同时我们处理出最大值所在的位置,额外用数组记录即可。
而对于后手,要求[L,R]最小且要赢,说明要找到两边区间内大于[l,r]中最大值且距离最近的位置。可以使用单调栈来预处理。
对于ai右边的最大值,我们维护一个单调递减栈,从左往右枚举,当栈头出栈时,当前数即为栈头右侧第一个比它大的数的位置,记录即可。
对于左侧同理。
找到左右两侧更大的数(或者找不到就是输),比较位置远近即可。
代码
C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
// 定义全局变量
int n, k; // 数组长度和查询次数
vector<int> elements, log_values; // 元素数组和log值数组
vector<vector<int>> sparse_table; // 稀疏表
vector<int> left_greater_indices, right_greater_indices; // 每个元素左边和右边第一个比它大的元素的索引
// 构建log值数组
void buildLogValues() {
for (int i = 2; i <= n; i++) {
log_values[i] = log_values[i / 2] + 1; // 通过前一个元素的log值计算当前元素的log值
}
}
// 构建稀疏表
void buildSparseTable() {
for (int i = 0; i < n; i++) {
sparse_table[i][0] = i; // 初始化稀疏表的第一列为元素的索引
}
int j = 1;
while ((1 << j) <= n) { // 根据区间长度迭代稀疏表的列
for (int i = 0; i <= n - (1 << j); i++) {
int left_index = sparse_table[i][j - 1]; // 左区间的最大值索引
int right_index = sparse_table[i + (1 << (j - 1))][j - 1]; // 右区间的最大值索引
sparse_table[i][j] = (elements[left_index] >= elements[right_index]) ? left_index : right_index; // 将较大值的索引存入稀疏表
}
j++;
}
}
// 在区间[left, right]中找到最大值的索引
int findMaxIndex(int left, int right) {
int span = log_values[right - left + 1]; // 计算区间长度的log值
int left_index = sparse_table[left][span]; // 左区间的最大值索引
int right_index = sparse_table[right - (1 << span) + 1][span]; // 右区间的最大值索引
return (elements[left_index] >= elements[right_index]) ? left_index : right_index; // 返回较大值的索引
}
// 计算每个元素左边和右边第一个大于它的元素的索引
void calculateGreaterIndices() {
right_greater_indices.assign(n, -1); // 初始化右侧第一个大于元素的索引数组
left_greater_indices.assign(n, -1); // 初始化左侧第一个大于元素的索引数组
vector<int> stack; // 用于存储索引的栈
// 计算右侧第一个大于该元素的索引
for (int i = 0; i < n; i++) {
while (!stack.empty() && elements[stack.back()] <= elements[i]) {
right_greater_indices[stack.back()] = i; // 更新右侧第一个大于该元素的索引
stack.pop_back(); // 弹出栈顶元素
}
stack.push_back(i); // 当前元素的索引入栈
}
stack.clear(); // 清空栈
// 计算左侧第一个大于该元素的索引
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && elements[stack.back()] <= elements[i]) {
left_greater_indices[stack.back()] = i; // 更新左侧第一个大于该元素的索引
stack.pop_back(); // 弹出栈顶元素
}
stack.push_back(i); // 当前元素的索引入栈
}
}
// 处理查询
void processQueries(const vector<int>& max_indices, int max_val_count) {
for (int i = 0; i < k; i++) {
int left, right;
cin >> left >> right;
left -= 1; // 转换为0-based索引
right -= 1; // 转换为0-based索引
int max_index = findMaxIndex(left, right); // 在区间[left, right]中找到最大值的索引
if (elements[max_index] == elements[max_indices[0]]) { // 如果区间最大值等于全局最大值
if (max_val_count >= 2) { // 如果全局最大值出现次数大于等于2次
cout << "draw" << endl;
int lower_bound_idx = lower_bound(max_indices.begin(), max_indices.end(), left) - max_indices.begin(); // 找到大于等于left的第一个最大值索引
int upper_bound_idx = upper_bound(max_indices.begin(), max_indices.end(), right) - max_indices.begin() - 1; // 找到小于等于right的最后一个最大值索引
if (lower_bound_idx < upper_bound_idx) {
cout << right - left + 1 << endl; // 如果在查询区间内有两个最大值,输出查询区间的长度
} else {
int adjustment = INT_MAX; // 初始化调整值
if (lower_bound_idx > 0) {
adjustment = min(adjustment, max_indices[lower_bound_idx] - left); // 计算调整值
}
if (upper_bound_idx < (int)max_indices.size() - 1) {
adjustment = min(adjustment, right - max_indices[upper_bound_idx]); // 计算调整值
}
cout << right - left + 1 + adjustment << endl; // 输出调整后的长度
}
} else {
cout << "lose" << endl;
cout << (left == right ? 2 : right - left + 1) << endl; // 如果全局最大值只有1次,输出"lose"并输出查询区间的长度
}
} else {
int left_boundary = (left_greater_indices[max_index] != -1) ? left_greater_indices[max_index] : -0x3f3f3f3f; // 左侧第一个大于max_index元素的索引
int right_boundary = (right_greater_indices[max_index] != -1) ? right_greater_indices[max_index] : 0x3f3f3f3f; // 右侧第一个大于max_index元素的索引
cout << "win" << endl;
cout << min(right_boundary - right, left - left_boundary) + right - left + 1 << endl; // 输出查询区间的长度
}
}
}
int main() {
std::ios::sync_with_stdio(false); // 提高输入输出效率
cin >> n >> k; // 输入数组长度和查询次数
elements.resize(n); // 调整元素数组大小
log_values.resize(n + 1, 0); // 初始化log值数组
sparse_table.assign(n, vector<int>((int)log2(n) + 1, 0)); // 初始化稀疏表
// 输入元素数组
for (int i = 0; i < n; i++) {
cin >> elements[i];
}
// 构建log值和稀疏表
buildLogValues();
buildSparseTable();
// 计算左右侧第一个大于元素的索引
calculateGreaterIndices();
int max_val = *max_element(elements.begin(), elements.end()); // 找到元素数组中的最大值
int max_val_count = count(elements.begin(), elements.end(), max_val); // 计算最大值的出现次数
vector<int> max_indices; // 存储最大值的所有索引
// 找出最大值的所有索引
for (int i = 0; i < n; i++) {
if (elements[i] == max_val) {
max_indices.push_back(i); // 如果当前元素等于最大值,存储它的索引
}
}
// 处理查询
processQueries(max_indices, max_val_count);
return 0;
}
题目内容
小明和小美在玩一个游戏,游戏中有一个长度为n的数组a,她们会玩q轮游戏,每轮游戏都是独立的。
游戏规则如下,双方都会执行最优策略:
1)第一步,游戏给出一个区间[l,r]。
2)第二步,小明在[l,r]区间中选择一个数。
3)第三步,小美将区间扩展成[L,R] ([L,R]必须包含[l,r]),然后在[L,R]区间中选择一个数,但不能跟小明选同一个数。
4)第四步,小明和小美选择的数字较大的一方获胜,若相同则平局。
小美想知道她每一轮的输赢状态,并且她想知道要达到输赢状态所需的[L,R]区间长度最小是多少。
输入描述
第一行输入两个正整数n,q(2≤n,q≤2×105),表示数组长度和询问次数。
第二行输入n个正整数a(1≤ai≤109),表示数组。
接下来q行,每行输入两个整数(1≤l≤r≤n),表示询问
输出描述
对于每个询问先输出一行,若小美可以获胜则输出”win“,若平局则输出”draw“,多失败则输出”lose“。
第二行输出达到最终状态所需的区间长度的最小值。
样例1
输入
6 2
1 1 4 5 1 4
1 3
4 4
输出
win
4
lose
2
说明
第1个询问,小明会选择数字4,小美将区间扩展成[1,4],选择数字5,小美获胜,扩展后的区间长度为4。
第2个询问,小明会选择数字5,小美将区间扩展成[3,4],选择数字4,小美获胜,扩展后的区间长度为2。