题目本身没什么题意难度，很好懂。也没什么算法难度，一看就知道是个排序和二分。但是写了就会发现是真难写。
子任务 1
只有一种类型 A，不用管类型了。直接按攻击力从小到排序。
- 如果 ，显然就是输出
lower_bound的位置。 - 如果 ，显然要么第一个小于等于 ，要么全都不小于，所以输出必然是 或 。
子任务 2
保证都是找第一个大于等于的位置。类型 A 和 C 就是子任务 1 的第一种情况。类型 B 就是子任务 1 的 第二种情况。
子任务 3
做法 1
如果按照三个武器类型 两种 类型，写 种情况的二分，那一不小心你就要写 行。当然 Gemini 就是这么写的，Gemini 的代码会放在题解最后。
做法 2
显然整体在抽象意义下也是有序的。而二分的核心无非就是：
mid满足条件时更新答案。- 如果需要去
mid左边找更优答案就r = mid - 1; - 如果需要去
mid右边找更优答案就l = mid + 1;
一般的二分我们会把 1 融入到 2,3 之一。这题我们拆开来就会非常好写了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
pair<char, int> a[MAXN + 5];
bool cmp(pair<char, int> x, pair<char, int> y)
{
if (x.first != y.first)
return x.first < y.first;
if (x.first == 'B')
return x.second > y.second;
return x.second < y.second;
}
// 当前符合要求
bool ok(char op, int x, char midOp, int midX)
{
// op == midOp 可以分配率一下，但是我想对齐，交给编译器优化
if (op == midOp && x >= 0 && midX >= x ||
op == midOp && x < 0 && midX <= -x)
return true;
return false;
}
// 需要去左边找更优解
bool lft(char op, int x, char midOp, int midX)
{
if (op != midOp)
return op < midOp;
if (op == 'A' || op == 'C')
{
// 升序
if (x >= 0) // 找第一个大于等于 x 的
return midX >= x;
else // 找第一个小于等于 -x 的
return true;
}
// 降序
if (x >= 0) // 找第一个大于等于 x 的
return true;
else // 找第一个小于等于 -x 的
return midX <= -x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1, cmp);
/*
for (int i = 1; i <= n; i++)
cout << a[i].first << " ";
cout << "\n";
for (int i = 1; i <= n; i++)
cout << a[i].second << " ";
cout << "\n";
*/
int Q;
cin >> Q;
while (Q--)
{
char op;
int x;
cin >> op >> x;
int l = 1;
int r = n;
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
char midOp = a[mid].first;
int midX = a[mid].second;
if (ok(op, x, midOp, midX)) // 当前符合要求
ans = mid;
if (lft(op, x, midOp, midX)) // 需要去左边找更优解
r = mid - 1;
else
l = mid + 1;
}
cout << ans << "\n";
}
return 0;
}
[Copy](javascript:;)
Gemini 的 100+ 行代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
// 主函数包含解题逻辑
void solve() {
// 使用快速 I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
// 分别用 vector 存储三类武器的攻击力
std::vector<int> a_weapons;
std::vector<int> b_weapons;
std::vector<int> c_weapons;
// 读取 n 把武器并按类型分组
for (int i = 0; i < n; ++i) {
char type;
int attack;
std::cin >> type >> attack;
if (type == 'A') {
a_weapons.push_back(attack);
} else if (type == 'B') {
b_weapons.push_back(attack);
} else { // type == 'C'
c_weapons.push_back(attack);
}
}
// 按照题目要求对各类武器进行排序
// 类型 A (近战): 攻击力从小到大
std::sort(a_weapons.begin(), a_weapons.end());
// 类型 B (射手): 攻击力从大到小
std::sort(b_weapons.begin(), b_weapons.end(), std::greater<int>());
// 类型 C (法师): 攻击力从小到大
std::sort(c_weapons.begin(), c_weapons.end());
int q;
std::cin >> q;
// 计算 B 和 C 类武器在最终排序列表中的起始位置（偏移量）
size_t a_size = a_weapons.size();
size_t b_offset = a_size;
size_t c_offset = a_size + b_weapons.size();
// 处理 Q 次查询
for (int i = 0; i < q; ++i) {
char type;
int x;
std::cin >> type >> x;
if (type == 'A') {
if (x >= 0) {
// 查找攻击力 >= x 的第一把武器
// lower_bound 返回第一个不小于 x 的元素的迭代器
auto it = std::lower_bound(a_weapons.begin(), a_weapons.end(), x);
if (it == a_weapons.end()) {
std::cout << 0 << "\n";
} else {
// 位置是 1-based 的，等于 0-based 的下标 + 1
std::cout << (it - a_weapons.begin()) + 1 << "\n";
}
} else {
// 查找攻击力 <= -x 的第一把武器
long long target = -x;
// A 升序排列，第一把武器攻击力最低。
// 如果它满足条件，那么它就是位置最靠前的答案。
if (a_weapons.empty() || a_weapons[0] > target) {
std::cout << 0 << "\n";
} else {
std::cout << 1 << "\n";
}
}
} else if (type == 'B') {
if (x >= 0) {
// 查找攻击力 >= x 的第一把武器
// B 降序排列，第一把武器攻击力最高。
// 如果它满足条件，那么它就是位置最靠前的答案。
if (b_weapons.empty() || b_weapons[0] < x) {
std::cout << 0 << "\n";
} else {
std::cout << b_offset + 1 << "\n";
}
} else {
// 查找攻击力 <= -x 的第一把武器
long long target = -x;
// B 降序排列，用 lower_bound 和 std::greater 查找第一个 e <= target 的元素。
auto it = std::lower_bound(b_weapons.begin(), b_weapons.end(), target, std::greater<int>());
if (it == b_weapons.end()) {
std::cout << 0 << "\n";
} else {
std::cout << b_offset + (it - b_weapons.begin()) + 1 << "\n";
}
}
} else { // type == 'C'
if (x >= 0) {
// 查找攻击力 >= x 的第一把武器
auto it = std::lower_bound(c_weapons.begin(), c_weapons.end(), x);
if (it == c_weapons.end()) {
std::cout << 0 << "\n";
} else {
std::cout << c_offset + (it - c_weapons.begin()) + 1 << "\n";
}
} else {
// 查找攻击力 <= -x 的第一把武器
long long target = -x;
// C 升序排列，逻辑同 A。
if (c_weapons.empty() || c_weapons[0] > target) {
std::cout << 0 << "\n";
} else {
std::cout << c_offset + 1 << "\n";
}
}
}
}
}
int main() {
solve();
return 0;
}
[Copy](javascript:;)