首页 > ACM题库 > HDU-杭电 > HDU 4217-Data Structure?-线段树-[解题报告]HOJ
2015
05-23

HDU 4217-Data Structure?-线段树-[解题报告]HOJ

Data Structure?

问题描述 :

Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you.
Original, there are N numbers, namely 1, 2, 3…N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.

Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N – i + 1

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.

Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N – i + 1

样例输入:

2
3 2
1 1
10 3
3 9 1

样例输出:

Case 1: 3
Case 2: 14

http://acm.hdu.edu.cn/showproblem.php?pid=4217

线段树,每个节点记录当前子树中还有多少个数。

//线段树
#include <stdio.h>

#define MAX 262145

int tmp;

typedef struct _tree
{
	int left;
	int right;
	int count;
}tree;

tree t[MAX*3];

void build_tree(int c, int left, int right)
{
	int mid;
	t[c].left = left;
	t[c].right = right;
	t[c].count = right - left + 1;
	if(left == right)return ;
	mid = (left + right)>>1;
	build_tree(2*c, left, mid);
	build_tree(2*c+1, mid+1, right);
}

void del(int c, int ki)
{
	if(t[c].left == t[c].right){
		tmp = t[c].right;
		t[c].count --;
		return;
	}
	if(ki <= t[2*c].count){	//if the left tree'count is less than ki then the ki-th min number must be at the left tree
		del(2*c, ki);
	}
	else {	//else it is at the right tree
		del(2*c+1, ki - t[2*c].count);
	}
	t[c].count --;
}

int main()
{
	int t, n, k, cas, ki;
	__int64 res;
	scanf("%d", &t);
	for(cas = 1; cas <= t; cas ++){
		scanf("%d%d", &n, &k);
		build_tree(1, 1, n);
		res = 0;
		while(k --){
			scanf("%d", &ki);
			del(1, ki);
			res += tmp;
		}
		printf("Case %d: %I64d\n", cas, res);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wchyumo2009/article/details/7560226