當前位置:首頁 > 資訊 > info6 > 正文

2451

發表于: 2014-05-24   作者:chen_xinjia   來源:轉載   瀏覽:
ZOJ
摘要: 點擊打開鏈接//這道題似乎是默認一定會成功的,而且是按大小順序輸入的? //#include"stdafx.h" #include #include #defineMAXN100001 #defineMAX500001 structnode { longx,y,w; }T[MAXN*2]; longN,M,S,Val; voidbuild(longp,longa,longb)//建樹 { T[p]

點擊打開鏈接

//這道 題似乎是默認一定會成功的,而且是按大小順序輸入的?
//#include "stdafx.h"
#include    <cstdio>
#include    <cstdlib>
#define     MAXN    100001
#define     MAX     500001
struct node
{
	long    x, y, w;
}   T[MAXN *2];
long    N, M, S, Val; 
void    build(long p, long a, long b)//建樹
{
	T[p].x = a; T[p].y = b; T[p].w = MAX;
	if (a + 1 < b)
	{
		build(p*2, a, a + b >> 1);
		build(p*2+1, a + b >> 1, b);
	}
}
void    update(long p)//將 0 到 S的 中比val大的線段 標志更新為 val
{
	if (T[p].w > Val)
		T[p].w = Val;
	if (T[p].x + 1 < T[p].y)
	if (S <= T[p].x + T[p].y >> 1)
		update(p*2);
	else
 		update(p*2+1);
}
long    query(long p, long a, long b)//找到 s  之前較小的標志
{
	if ((a <= T[p].x) && (T[p].y <= b))//如果 包含 則返回
		return T[p].w;
	long    mid = T[p].x + T[p].y >> 1;
	if (b <= mid)// 左子樹
		return query(p*2, a, b);
	if (mid <= a)//右子樹
		return query(p*2+1, a, b);
	//左右子樹都有包含的時候
	long    t1 = query(p*2, a, mid);
	long    t2 = query(p*2+1, mid, b);
	return t1 < t2 ? t1 : t2;
}
int     main()
{
	long    temp;
	while (scanf("%ld%ld", &N, &M) != EOF)
	{
		build(1, 0, N);//0 到 40建樹 ,1為 初始下標
		S = 1; Val = 0;
		update(1);
		while (M--)
		{
			scanf("%ld%ld", &temp, &S);
			Val = query(1, temp - 1, S - 1) + 1;//temp-1是因為題是從0開始建樹的,s-1是因為搜索s的前一個線段的標志是為多少
			update(1);//從下標1的地方 開始更新
		}
		printf("%ld\n", query(1, N - 1, N));
	}
	return 0;
}

好吧,我只是勤勞的搬運工,誰叫自己上課不好好聽的。。。。理解也理解了很久呀!!!!

2451

版權所有 IT知識庫 CopyRight ? 2009-2015 IT知識庫 IT610.com , All Rights Reserved. 京ICP備09083238號
广东25选5开奖结果