程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4343 Interval query(倍增思想+貪心)

HDU 4343 Interval query(倍增思想+貪心)

編輯:C++入門知識

HDU 4343 Interval query(倍增思想+貪心)


題意:給定n(n<=100000)個區間(左閉右開)和m(m<=100000)次詢問[l, r],問所有在[l, r]區間內最多有多少個兩兩不相交的區間。,

思路:首先貪心的思想,去除掉包含其他區間的大區間,這樣做肯定不會影響結果。

然後對於所有區間,按照左端點升序排序,那麼由於這時所有區間不相互包含,他們的右端點也是遞增的。

那麼對於每個詢問,肯定是從左到右去盡可能多的區間,這個貪心容易想到。

對數據離散化,記錄從每個點開始的經過i個區間所達到的最近距離,這一步用到了倍增的思想,因為如果一個點一個點順序找,那麼時間復雜度和空間復雜度都無法承受。

具體來說,用f[i][j]記錄從i出發經過2^j個區間所達到的最近點,那麼可以得出遞推關系

f[i][j] = f[ f[i][j-1] ][j-1];

那麼對於每個詢問,我們將詢問ql,qr也離散化,只需找到從ql最多經過多少區間使得其不超過qr即可。

ps:半夜睡不著真是心痛,起來補題.........

 

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
#define pii (pair)
//#pragma comment(linker, /STACK:1024000000,1024000000) 
using namespace std;  

const int maxn = 100000 + 100;
const int INF = 0x3f3f3f3f;
int n, m;
struct Node {
	int l, r;
	bool operator < (const Node& A) const {
		if(l == A.l) return r > A.r;
		return l < A.l;
	}
} node[maxn]; 
int discret[2*maxn];
int fa[2*maxn][20];

int solve(int l, int r) {
	int ans = 0;
	for(int i = 16; i >= 0; i--) {
		int t = fa[l][i];
	//	cout << t << endl;
		if(t == r) return ans+(1<= 0; i--) {
		//	cout << node[i].l << endl;
			if(i == node[cnt2].l) {
				fa[i][0] = min(node[cnt2].r, fa[i+1][0]);
				while(i == node[cnt2].l) cnt2--;
			}
			else fa[i][0] = fa[node[cnt2+1].l][0];
		}
		for(int i = 1; i < 17; i++) {
			for(int j = 0; j < cnt; j++) if(fa[j][i-1] != INF) fa[j][i] = fa[ fa[j][i-1] ][i-1];
		}
		for(int i = 0; i < m; i++) {
			int l, r; scanf(%d%d, &l, &r);
			l = lower_bound(discret, discret+cnt, l) - discret;
			r = upper_bound(discret, discret+cnt, r) - discret - 1;
	//		cout << l <<   << r << endl;
			printf(%d
, solve(l, r));
		}
	//cout << fa[0][0] << endl;
	}
	return 0;
}



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved