기초 이분

1432 단어 두 번째
1. 조건에 맞는 최대치를 찾는다(즉 왼쪽 답안이 합법적이다)
while(r>l)
{
	int mid=l+(r-l+1)/2;//      
	if(true)
	{
		l=mid;
	} 
	 else
	{
		r=mid-1; 	
	}
 } 

2. 조건에 부합되는 최소치를 찾는다(즉 오른쪽 답안이 합법적이다)
while(r>l)
{
	int mid=l+(r-l)/2;//      
	if(true)
	{
		r=mid;
	} 
	 else
	{
		l=mid+1; 	
	}
 } 

3. 부동점수의 2점
4
1.
while(r-l>eps)
{
	
}
2.
for(int i=1;i<=100;i++)
{
	
}
첫 번째 쓰기는 부동점수의 정밀도 때문에 사순환에 빠지기 쉽다. 두 번째 순환의 100번의 정밀도는 대략
10
−30
10
−30
10의 마이너스 30회
예제
CodeForces - 732D
여기 의 이분 검사 과정 은 뒤 에서 앞 으로 첫 번째 틀 을 덧씌운다
#include
#include
#include
using namespace std;
int a[100001];
int q[100001];
int vis[100001]; 
int ok;
int n,k;
int check(int x)
{
	memset(vis,0,sizeof(vis));
	int sum=0;
	int v=0;
	for(int i=x;i>=1;i--)
	{
		if(a[i]==0)
		{
			if(sum>0) sum--;
			continue;
		}
		if(vis[a[i]]==0)
		{
			vis[a[i]]=1;
			v++;
			sum+=q[a[i]];
		}
		else if(sum>0)
		{
			sum--;
		}
	}
	if(sum>0) return 0;
	if(v>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=k;i++)
		cin>>q[i];
	int l=1,r=n+1;
	ok=0;
	while(r>l)
	{
		int mid=(l+r)/2;
		if(check(mid))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	 }
	if(ok) cout<

좋은 웹페이지 즐겨찾기