qswl,首AC但WA了四次
2024-05-16 22:32:16
发布于:浙江
61阅读
0回复
0点赞
本是标准二分+结构体版子,可惜橡皮是蒟蒻,WA了4次
错误历程:
先是直接用lower_bound的,但发现会有两个点WA,两次才发现问题,它好像是无序的......
然后我本来想用sort直接排,这次提前找到了问题,排完后原顺序会变
没输出id错了一次后以为二分打错了,调教二分又错了一次......
最后找半天才改对
上代码:
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}//快读YYDS
struct Node {int id, num;};
bool cmp(Node x, Node y) {
return x.num < y.num;
}//没用结构体排能对8个点,但没法AC
int main() {
int n = read(), m;
Node a[n + 1];
for (int i = 1; i <= n; ++i)a[i].num = read(), a[i].id = i;//初始化
sort(a + 1, a + n + 1, cmp);
m = read();
while (m--) {
int tmp = read();
int l = 1, r = n;
while (l < r) {//左开区间
int mid = l + r >> 1;
if (a[mid].num >= tmp)r = mid;
else l = mid + 1;
}
if (a[l].num == tmp)cout << a[l].id/*注意是输出id,错过一次(悲)*/ << endl;//本来想直接用lower_bound的,但结构体没法用(悲
else cout << 0 << endl;//记得特判输出0
}
return 0;
}
欢迎来三体ACGO分部
这里空空如也
有帮助,赞一个