POJ 1201 Intervals (차동 제약 시스템, 욕심 + 선분 트 리)

제목 유형  차동 제약 시스템, 욕심 + 선분 트 리
제목
최대 50000 개의 정수 구간 과 이 구간 에 적어도 포 함 된 정수 의 개 수 를 요구 합 니 다.
지금 은 원소 의 수량 이 가장 적은 정수 집합 을 찾 아 상기 조건 을 만족 시 키 고 가장 적은 원소 의 개수 가 얼마 인지 물 어 봐 야 한다.
문제 풀이 방법
방법 1 차 제약 시스템
d [i] 는 0 - > i - 1 구간 에 포 함 된 정수 의 개 수 를 나타 낸다.
그러면 그 중의 한 조건 l, r, c 는 d [r + 1] - d [l] > = c 를 나타 낸다.
그리고 추가 조건 0 < = d [i] - d [i - 1] < = 1 즉 d [i] - d [i - 1] > = 0, d [i - 1] - d [i] > = - 1 구체 적 인 건축 도 보기 코드
방법 2 욕심 + 선분 수
먼저 입력 한 조건 을 오른쪽 단점 에 따라 작은 것 부터 큰 것 까지 정렬 합 니 다.
그리고 어떤 조건 을 처리 할 때 l - > r 사이 에 이미 몇 개의 수가 구조의 집합 에 있 는 지 조회 합 니 다. 만약 에 이 수량 이 요구 하 는 수량 보다 크 거나 같 으 면 처리 하지 않 아 도 됩 니 다.
작 으 면 r - > l 순 으로 선택 하지 않 은 정 수 를 선택 하 세 요.
이렇게 하면 뒤에 선택 한 수 를 최대한 적 게 할 수 있 기 때문에 이곳 의 조회 와 업 데 이 트 는 선분 트 리 최적화 시간 에 코드 를 구체 적 으로 봐 야 합 니 다.
참조 코드 - 궁금 한 점 이 있 으 시 면 아래 에 댓 글 을 남 겨 주시 면 바로 답 해 드 리 겠 습 니 다.
방법 1 코드

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1<<29;
const int maxn = 50000 + 10;

int d[maxn], L, R;
bool vis[maxn];
vector<int>E[maxn];
vector<int>W[maxn];

void spfa() {
	memset(vis, 0, sizeof(vis));
	for( int i=L; i<=R+1; i++ ) d[i] = -INF;
	d[R+1] = 0;
	vis[R+1] = 1;
	queue<int>q;
	q.push(R+1);
	while(!q.empty()) {
		int f = q.front(); q.pop(); vis[f] = false;
		//printf("f = %d
", f);
		for( int i=0; i<E[f].size(); i++ ) {
			int v =  E[f][i], w = W[f][i];
			if(d[v] < d[f] + w) {
				d[v] = d[f] + w;
				//printf("v = %d d[v] = %d
", v, d[v]);
				if(vis[v] == false) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
		if(f < R && d[f] > d[f+1]) { //　       
			d[f+1] = d[f];
			if(vis[f+1] == false) {
				vis[f+1] = true;
				q.push(f+1);
			}
		}
		if(f > L && d[f] - 1 > d[f-1]) {
			d[f-1] = d[f] - 1;
			if(vis[f-1] == false) {
				vis[f-1] = true;
				q.push(f-1);
			}
		}
	}
}

int main() {
	freopen("in", "r", stdin);
	int n;
	while(scanf("%d", &n) != EOF) {
		L = INF, R = -INF;
		for( int i=0; i<=maxn+2; i++ ) E[i].clear(), W[i].clear();
		for( int i=0; i<n; i++ ) {
			int l, r, c;
			scanf("%d%d%d", &l, &r, &c);
			//E[l] d[r+1] - d[l] >= c　       
			E[l].push_back(r+1);
			W[l].push_back(c);
			L = min(L, l);
			R = max(R, r+1);
		}
		int rt = R + 1;
		for( int i=L; i<=R; i++ ) {
			/*if(i != R) {
				E[i].push_back(i+1);
				W[i].push_back(0);
			}
			if(i != L) {
				E[i].push_back(i-1);
				W[i].push_back(-1);
			}*/ //        spfa         
			E[rt].push_back(i);
			W[rt].push_back(0);
		}
		spfa();
		printf("%d
", d[R]);
	}
	return 0;
}

방법 2 코드

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mid ((l+r)>>1)
const int INF = 1<<29;
const int maxn = 50000 + 10;

int N[maxn*4];
bool all[maxn*4];

struct Node {
	int l, r, c;
	bool operator < (const Node & rhs) const {
		if(r == rhs.r) return c > rhs.c;
		else return r < rhs.r;
	}
}a[maxn];

void pushdown(int rt, int l, int r) {
	if(l == r) return ;
	if(all[rt]) {
		N[ls] = mid-l+1;
		N[rs] = r - mid;
		all[ls] = all[rs] = true;
		all[rt] = false;
	}
}

int query(int rt, int l, int r, int L, int R) {
	pushdown(rt, l, r);
	if(l == L && r == R) return N[rt];
	if(R <= mid) return query(ls, l, mid, L, R);
	else if(L > mid) return query(rs, mid + 1, r, L, R);
	else return query(ls, l, mid, L, mid) + query(rs, mid + 1, r, mid + 1, R);
	N[rt] = N[ls] + N[rs];
}

void update(int rt, int l, int r, int x, int c) {
	pushdown(rt, l, r);
	//printf("%d %d %d x = %d c = %d
", rt, l, r,x, c);
	if(r-l+1-N[rt] == c) {
		N[rt] = r-l+1;
		all[rt] = true;
		return ;
	}
	if(x <= mid) update(ls, l, mid, x, c);
	else {
		int tn = query(1, 0, maxn-10, mid+1, min(r,x));
		tn = min(r,x)-mid-tn;
		//printf("tn = %d
", tn);
		if(tn < c) {
			update(ls, l, mid, x, c - tn);
			update(rs, mid + 1, r, x, tn);
		}
		else update(rs, mid + 1, r, x, c);
	}
	N[rt] = N[ls] + N[rs];
}

int main() {
	freopen("in", "r", stdin);
	int n;
	while(scanf("%d", &n) != EOF) {
		memset(N, 0, sizeof(N));
		memset(all, 0, sizeof(all));
		for( int i=0; i<n; i++ ) {
			int l, r, c;
			scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].c);
		}
		sort(a, a + n);
		for( int i=0; i<n; i++ ) {
			int num = query(1, 0, maxn-10, a[i].l, a[i].r);
			if(num >= a[i].c) continue;
			a[i].c -= num;
			update(1, 0, maxn-10, a[i].r, a[i].c);
		}
		printf("%d
", N[1]);
	}
	return 0;
}