16pts求条
查看原帖
16pts求条
1401754
floris楼主2024/12/18 10:14

用暴力方法+一点小优化做的,过了%80的点但由于subtask 只有16pts,希望各位大佬能帮忙找一下哪里还有漏洞

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int n;
struct node{
	int x,p,d;
}e[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>e[i].x>>e[i].p>>e[i].d;
	}
	int dir=0,flg=0;
	for(int i=1;i<n;i++){
		if(e[i].p<e[i+1].x-e[i].x&&e[i+1].p<e[i+1].x-e[i].x&&e[i].p+e[i+1].p>=e[i+1].x-e[i].x){
			if(flg==1){
				cout<<-1<<'\n';
				return 0;
			}
			else{
				dir=i;flg=1;
			}
		}
		else if(e[i].p+e[i+1].p<e[i+1].x-e[i].x){
			cout<<-1<<'\n';
			return 0;
		}
	}
	if(dir>0){
		int ans=0;
		for(int i=1;i<=dir;i++){
			if(e[i].d!=1) ans++;
			if(e[i].p<e[i+1].x-e[i].x&&i!=dir){
				cout<<-1<<'\n';
				return 0;
			}
		}
		for(int i=dir+1;i<=n;i++){
			if(e[i].d!=-1) ans++;
			if(e[i].p<e[i].x-e[i-1].x&&i-1!=dir){
				cout<<-1<<'\n';
				return 0;
			}	
		}
		cout<<ans<<'\n';
		return 0;
	}
	else{
		bool fl1=0,fl2=0;
		int an1=0,an2=0;
		for(int i=1;i<=n;i++){
			if(e[i].d==1) an1++;
			if(e[i].p<e[i].x-e[i-1].x) fl1=1;
		}
		for(int i=1;i<=n;i++){
			if(e[i].d==-1) an2++;
			if(e[i].p<e[i+1].x-e[i].x) fl2=1;
		}
		if(fl1==1&&fl2==1) cout<<-1<<'\n';
		else if(fl1==1&&fl2==0) cout<<an2<<'\n';
		else if(fl2==1&&fl1==0) cout<<an1<<'\n';
		else cout<<min(an1,an2)<<'\n';
	}
	return 0;
}
2024/12/18 10:14
加载中...