自己考场写的抽象代码,感觉思路大体上对了
查看原帖
自己考场写的抽象代码,感觉思路大体上对了
897873
lwthree楼主2024/11/9 15:57

,但是运行全部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;
	}
}

2024/11/9 15:57
加载中...