,但是运行全部RE+TLE让我非常悲伤,求佬指出错误 代码如下+我的解释:
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int d[MAXN],v[MAXN],a[MAXN];
int p[MAXN];
int n,m,L,V;
struct drive{
int l,r;
}thought[MAXN];
// 用于第二问的排序
bool thcmp(drive a,drive b){
return a.l<b.l;
}
// 就是超速(也就是需要考虑的l,r)(第二问)
int poss;
// check1~3用于第一问的判断,(二分会写但忘记),check4用于第二问检测当前的摄像头是不是可以检测到现在的超速的车
bool check1(int x){
for (int j=1;j<=m;j++){
if (p[j]>=x){
return true;
}
}
return false;
}
bool check2(int x){
for (int j=1;j<=m;j++){
if (p[j]<=x){
return true;
}
}
return false;
}
bool check3(int x,int y){
for (int j=1;j<=m;j++){
if (x<=p[j]&&p[j]<=y) {
return true;
}
}
return false;
}
bool check4(int s,int i){
if (thought[i].l<=p[s]&&p[s]<=thought[i].r) return true;
return false;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
int T;cin>>T;
while (T--){
cin>>n>>m>>L>>V;
int cnt=0;
int poss=0;
for (int i=1;i<=n;i++) cin>>d[i]>>v[i]>>a[i];
for (int i=1;i<=m;i++) cin>>p[i];
// 回答第一问并且计算第二问需要的区间和超速数量
for (int i=1;i<=n;i++){
if (a[i]>0){
if (v[i]>V){
if (check1(d[i])) {
cnt++;
thought[++poss]=(drive){d[i],L};
}
}
else {
float pos=(V*V-v[i]*v[i]) / (2*a[i]);
pos=(int)(pos+1);
if (check1(pos+d[i])&&(pos+d[i])<=L){
cnt++;
// thought即为第二问需要考虑的超速的车的行驶区间
thought[++poss]=(drive){pos+d[i],L};
}
}
}
else if (a[i]==0){
if (v[i]<=V) continue;
if (check1(d[i])) {
cnt++;
thought[++poss]=(drive){d[i],L};
}
}
else {
if (v[i]<V){
continue;
}
else{
int pos=(V*V-v[i]*v[i]) / (2*a[i]);
if (check3(d[i],d[i]+pos)) {
cnt++;
if (d[i]+pos>=L) thought[++poss]=(drive){d[i],L};
else thought[++poss]=(drive){d[i],d[i]+pos};
}
}
}
}
cout<<cnt<<' ';
// 这里开始是第二问
sort(thought+1,thought+n+1,thcmp);
int pl=0,pr=0;
// 先查找l最左边的thought的l和r来开始决策
for (int j=1;j<=m;j++){
if (p[j]>=thought[1].l){
pl=j;break;
}
}
for (int j=m;j>=1;j++){
if (p[j]<=thought[1].r){
pr=j;break;
}
}
// 这里是我最无法理解的地方???????到底哪里错了
// 意思是考虑每一个按照.l从小到大排序的thought,如果此时pl(即考虑的最左侧的摄像头)的值小于thoughti.l则继续寻找能用上的摄像头当做最左侧,如果此时左侧大于右侧说明至少需要再用一个摄像头,所以cnt2++并且
// 将pr更新到当前thoughti.r的能使用的最右侧的摄像头,最后再缩小pr的值,使其始终表示最右侧的最小值(对于每一个pl相同的范围内)
// 总体思想感觉和题解差不多,但是我本来考虑的是类似单调对列的想法
// 最后的 pl<pr 则++感觉不需要,因为每次++考虑的是之后需要的摄像头,但是删掉答案也不对就算了
int cnt2=1;
for (int i=2;i<=poss;i++){
while (!check4(pl,i)) pl++;
if (pl>pr) {
cnt2++;
while(!check4(pr,i)) pr++;
continue;
}
while (!check4(pr,i)) pr--;
}
if (pl<pr) cnt2++;
// cnt2为需要的摄像头,所以要减去为结果
cout<<m-cnt2<<endl;
}
}