기초 이분
1432 단어 두 번째
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<