AC第一个点
查看原帖
AC第一个点
1083200
guojiahong楼主2024/3/8 13:08
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> > q;
bool z=1,f=1,_z=1,_f=1;
bool l(int i,int len)
{
	bool b1=1,b2=1;
		for(int j=n-2;j>=0;j--)
		{
			if(q[j].first*q[j].second+q[j].second*i>q[n-1].first*q[n-1].second+q[n-1].second*i)
			{
				b1=0;
				break;
			}
		}
		if(!b1)
		{
			if(i>-1)f=0;
			if(i<1)_f=0;
		}
		for(int j=n;j<len;j++)
		{
			if(q[j].first*q[j].second+q[j].second*i>q[n-1].first*q[n-1].second+q[n-1].second*i)
			{
				b2=0;
				break;
			}
		}
		if(!b2)
		{
			if(i>-1)z=0;
			if(i<1)_z=0;
		}
		if(b1&&b2)
		{
			cout<<i;
			return 1;
	 	}
	return 0;
}
int main(){
	cin.tie(0);cout.tie(0);
	cin>>n;
	int a,b;
	int t;
	int a1,b1;
	cin>>a1>>b1;
	q.push_back({0,b1});
	for(int i=1;true;i++)
	{
		cin>>a>>b;
		if(a==-1&&b==-1)break;
		if(a<=n)q.push_back({a-a1,b});
		if(a==n)t=i;
	}
	int len=q.size();
	n=len;
	swap(q[t].first,q[n-1].first);
	swap(q[t].second,q[n-1].second);
	int h;
	cin>>h;
	pair<int,int> t1;
	t1.first=q[n-1].first;
	t1.second=q[n-1].second;
	for(int i=1;t1.second-i*h>=0;i++)
	{
		t1.second-=i*h;
		t1.first+=i;
		if(t1.first>0)q.push_back({t1.first,t1.second});
	}
	len=q.size();
	if(l(0,len))return 0;
	if(!z&&!f&&!_z&&!_f)
	{
		cout<<"NO SOLUTION";
		return 0;
	}
	for(int i=1;true;i++)
	{
		if(z||f)if(l(i,len))return 0;
		if(_z||_f)if(l(-i,len))return 0;
		if(!z&&!f&&!_z&&!_f)
		{
			cout<<"NO SOLUTION";
			return 0;
		}
	}
}
2024/3/8 13:08
加载中...