이분법 의 응용
4831 단어 이분 과 보 집 전환
쉽게 말 하면 [a, b] 구간 에서 F (x) > K 의 첫 번 째 x 를 요구 할 때 f (x) 구간 만족 [a, b]
안 이 단조롭다.해 를 찾 을 때 까지 절 차 를 반복 할 수 있다.
1. 현재 구간 의 중점 S 를 선택 하고 f (s) 를 계산 합 니 다.
2. f (s) > x 라면 3 단계 로 뛰 고 그렇지 않 으 면 4 단계 로 뛰 어 갑 니 다.
3. 현재 구간 을 [s, b] 로 바 꾸 고 5 단계 로 건 너 뛰 기
4. 현재 구간 을 [a, s] 로 전환 하여 5 단계 로 건 너 뛰 기
5. 현재 구간 이 구 해 요 구 를 만족 시 켰 다 면 물 러 나 지 않 으 면 첫 번 째 단계 로 넘 어 갑 니 다.
2 분 마다 원래 구간 을 절반 으로 줄 이기 때문에 시간 복잡 도 는 log * 판정 시간 이다.
이분법 이 문제 에서 의 응용 가 치 는 단조 로 운 구간 에서 극 치 를 구 하 는 문 제 를 판정 적 인 문제 로 바 꾸 는 것 이다.이것 은 직접적 으로 할 수 없 는 많은 문 제 를 간단하게 만 들 었 다.다음은 몇 가지 예 를 들 겠 습 니 다.
（1） 예제 1:
순서대로 N 개의 수 를 제시 하고 M 조 의 연속 적 인 요소 세그먼트 로 나 누 어 세그먼트 내 요소 의 가중치 와 가장 큰 요소 세그먼트 의 요소 의 가중치 와 최소 화 를 요구 합 니 다.보증 권 치 는 모두 양수 다.（1<=M<=N<=1000000）
처음 보 니 이 문 제 는 N ^ 2 * M 의 동적 계획 이 었 으 나 시간 복잡 도가 매우 심 했다.
그럼 어떻게 처리 해 야 하나 요?
2 점!우리 가 이런 문제 에 직면 했 을 때, 문 제 는 많이 간단 해 질 것 이다.
전환 후의 문제: 순서대로 N 개의 수 를 제시 하고 최소 그룹의 연속 적 인 요소 세그먼트 로 나 누 어 모든 요소 세그먼트 안의 요소 의 가중치 의 합 을 K 보다 작 거나 같 게 해 야 합 니 다.
전환 후의 문제 에 직면 하여 우 리 는 욕심 을 내 서 처리 할 수 있다 는 것 을 발견 했다.가능 한 한 각 그룹 을 채 우 고 넣 을 수 없 는 요소 나 최소 그룹 이 M 보다 크 면 안 된다 고 판단 하고 그렇지 않 으 면 줄 로 판단 합 니 다.상기 방법 에 따라 프로그램 을 작성 하면 시간 복잡 도 는 O (logLimit * N) 이 고 동적 계획 에 비해 알고리즘 이 너무 좋 습 니 다.
#include
#include
#include
using namespace std;
#define ULL unsigned long long
int n,m;
ULL l,r;
int s[1000010];
int num[1000010];
int maxn[1000010];
ULL MAXN;
ULL ans=18446744073709551615ULL;
bool pan(int l){
int i=0,cnt=1;
ULL sum=0;
while(1){
i++;sum+=s[i];
if(sum>l){
if(s[i]>l)return false;
sum=s[i];
cnt++;
if(cnt>m)return false;
}
if(i==n)break;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&s[i]),MAXN+=s[i];
l=1;r=MAXN;
while(l<=r){
ULL mid=(l+r)/2;
bool flag=pan(mid);
if(flag){
if(ans>mid)ans=mid;
if(l==r)break;
r=mid;
}
else l=mid+1;
}
printf("%I64u
",ans);
return 0;
} （2） 예제 2:
일대권 무 방향 그림 G 를 지정 합 니 다. 그 중에서 N 개의 점 과 M 개의 변 을 포함 하고 각 변 에 두 개의 가중치 A 와 B 가 있 습 니 다. 지금 은 두 개의 점 S 와 T 를 지정 하고 S 에서 T 까지 의 경 로 를 구하 여 경로 의 가중치 A 와 가중치 B 의 합 을 최소 화 합 니 다.이 최소 비율 을 구하 세 요.（N<=1000,M<=40000）
우선 동적 계획 으로 만 할 수 있 을 것 같 고 시간 복잡 도가 폭발 적 이다.
다시 모형 을 바 꿔 라.
전환 후의 문제:
비율 K 를 지정 하고 권한 이 없 는 그림 G 에 S 에서 T 까지 의 경로 가 존재 하 는 지 물 어보 면 이 경로 의 가중치 A 와 가중치 B 의 합 이 K 보다 크 지 않 습 니 다.
이 문 제 는 하기 어 려 울 것 같 지만 우 리 는 다음 과 같은 전환 을 할 수 있다.모든 변 (u, v, a, b) 에 대해 우 리 는 가중치 wi = ai - bi * k 를 사용 합 니 다.따라서 S 에서 T 까지 하나의 경로 가 존재 하여 새로운 가중치 와 0 보다 작 을 때 S 에서 T 까지 의 경로 가 반드시 존재 하여 그 비율 을 K 보다 작 게 한다.그러면 가장 짧 은 경 로 를 취해 0 과 비교 하 는 것 이 가장 좋 기 때문에 문 제 는 가장 짧 은 문제 가 된다.
#include
#include
#include
#include
using namespace std;
struct Edge{
int l,r,a,b;
};
queueq;
Edge ins[40010];
int head[1010],data[80010],nxt[80010];
double wei[80010];
int cn[1010];
double from[1010];
bool in[1010];
double dis[1010];
double k,l=0,r=10000,ans=100000;
int n,m,s,t,cnt;
void add(int x,int y,double weight){
nxt[cnt]=head[x];wei[cnt]=weight;data[cnt]=y;head[x]=cnt++;
nxt[cnt]=head[y];wei[cnt]=weight;data[cnt]=x;head[y]=cnt++;
}
bool spfa(){
memset(dis,65,sizeof dis);
memset(in,0,sizeof in);
memset(from,0,sizeof from);
memset(cn,0,sizeof cn);
dis[s]=0;in[s]=true;q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();in[now]=false;
for(int i=head[now];i;i=nxt[i]){
if(dis[data[i]]>dis[now]+wei[i]){
from[data[i]]=wei[i]+from[now];
dis[data[i]]=dis[now]+wei[i];
cn[data[i]]++;
if(cn[data[i]]==n+1)return true;
if(!in[data[i]]){
in[data[i]]=true;
q.push(data[i]);
}
}
}
}
if(from[data[t]]<=0)return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d%d",&ins[i].l,&ins[i].r,&ins[i].a,&ins[i].b);
scanf("%d%d",&s,&t);
while(r-l>=1e-10){
k=(l+r)/2;
cnt=1;
memset(head,0,sizeof head);memset(nxt,0,sizeof nxt);
memset(wei,0,sizeof wei);memset(data,0,sizeof data);
for(int i=1;i<=m;i++)add(ins[i].l,ins[i].r,ins[i].a-ins[i].b*k);
bool flag=spfa();
if(flag){
if(ans>k)ans=k;
if(r==k)break;
r=k;
}
else{
if(l==k)break;
l=k;
}
}
printf("%lf
",ans);
return 0;
} 상기 두 가지 예 제 를 통 해 우 리 는 이분법 의 관건 은 알 수 없 는 변 수 를 이미 알 고 있 는 것 으로 바 꾼 다음 에 이미 알 고 있 는 변수 로 알 수 없 는 변 수 를 평가 하 는 것 이다.그 중에서 두 드 러 진 사상 은 모델 의 전환 과 이용 이기 때문에 이분법 은 상당히 보편적 이 고 재 미 있 는 알고리즘 이다.
좋은 웹페이지 즐겨찾기
