题目没说 x≤y 吧
by yiyi049 @ 2021-08-28 23:13:44
@[doctor049](/user/518124) 是这样吗?
```cpp
if(x<=y){
for(int j=x;j<=y;j++){
b[t]=a[j];
t++;
}
}
else{
for(int j=y;j<=x;j++){
b[t]=a[j];
t++;
}
}
```
结果还是3个WA7个TLE啊
by easyf12 @ 2021-08-28 23:22:18
请读题:
“要询问在时间[x,y]内海浪高度第k小的单位时刻是**哪个时刻**”
询问的不是高度,而是时刻!
写了个结构体排序,供参考。
```cpp
#include <bits/stdc++.h>
using namespace std;
struct node{
int id,h;
}b[4010];
int a[4010];
bool cmp(node a,node b){
if(a.h==b.h) return a.id<b.id;
return a.h<b.h;
}
int t;
int main(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
int x,y,k;
cin>>x>>y>>k;
t=0;
for(int j=x;j<=y;j++){
b[t].id=j;
b[t].h=a[j];
t++;
}
sort(b,b+t,cmp);
cout<<b[k-1].id<<endl;
}
return 0;
}
```
by ycw123 @ 2021-08-28 23:57:29
上面的代码是解决 WA 问题的,关于 TLE 建议您可以将 $b$ 先排序,对于每个询问 $O(n)$ 扫一遍,若在 x—y 之间就 `cnt++`。当 $cnt=k$ 时就找到了第 $k$ 小的单位时刻
by ycw123 @ 2021-08-29 00:10:13
@[ycw123](/user/226844) 谢谢大佬!
by easyf12 @ 2021-08-29 12:10:26
@[ycw123](/user/226844) 我过了^_^
by easyf12 @ 2021-08-29 15:12:37