WUSTOJ 1337: Car race game（C）樹狀數組，離散化

題目連結：1337: Car race game

參考資料：⑴ Car race game 樹狀數組 棋煜，⑵ 樹狀數組，⑶ 離散化

補充資料：⑴ qsort，⑵ 二分查找

Description

Bob is a game programming specialist. In his new car race game, there are some racers(n means the amount of racers (1<=n<=100000)) racers star from someplace(xi means Starting point coordinate),and they possible have different speed(V means speed).so it possibly takes place to overtake(include staring the same point ). now he want to calculate the maximal amount of overtaking.

有 n 名參賽者，每名參賽者從自己的位置（Xi）以速度（Vi）勻速運動，問最後有多少次超越？

Input

The first line of the input contains an integer n-determining the number of racers. Next n lines follow, each line contains two integer Xi and Vi.(xi means the ith racer’s Starting point coordinate, Vi means the ith racer’s speed.0<Xi, Vi<1000000).

Output

For each data set in the input print on a separate line, on the standard output, the integer that represents the maximal amount of overtaking.

Sample Input

2
2 1
2 2
5
2 6
9 4
3 1
4 9
9 1
7
5 5
6 10
5 6
3 10
9 10
9 5
2 2
           

Sample Output

1
6
7
           

分析?

資料規模已經達到 100000，用普通做法：先輸入，按位置升序，比較速度，個數加1，，這種雙循環是會逾時的。

更好的思路是采用樹狀數組和離散化來處理此題。相信看完百科，大家對這兩個算法都有所了解。

以Simple Input的第3組資料為例說明：

• racer[]

  如下：

i	1	2	3	4	5	6
racer[i].x	5	6	5	3	9	9	2
racer[i].v	5	10	6	10	10	5	2

• 構造新速度

  speed[]

  ，i 就是新速度，如下：

i	1	2	3	4
speed[i]	2	5	6	10

• 離散化後，

  racer[]

  如下：

i	1	2	3	4	5	6
racer[i].x	5	6	5	3	9	9	2
racer[i].v	2	4	3	4	4	2	1

• 樹狀數組

  tree[]

  儲存的是對應區間的速度的人數。

i	tree[i]
1	A1
2	A1+A2
3	A3
4	A1+A2+A3+A4

這裡的

A[]

儲存的是每種速度的已添加的人數，在代碼中

A[]

并不需要，隻要

tree[]

即可。

• 參賽者排序是為了保證每名參賽者隻能超越自己前面的速度比自己小的人。否則樹狀數組就沒意義了。
• 注意，最壞的情況是每個人都能超越他前面的，那麼

  ans

  最大為 99999+99998+L+2+1=4999950000，超過了

  int

  的範圍，是以結果應該使用

  long long

  型

C代碼?

/*******************************************************************************
	Problem:	1337
	Language:	C
	Result:		Accepted
	Time:		629ms
	Memory:		3432 kb
	Author:		wowpH
	Version:	2.0
	Date:		2019-7-1 17:05:14
*******************************************************************************/
#include<stdio.h>
#include<stdlib.h>										//qsort()頭檔案
#include<memory.h>										//memset()頭檔案

int numberOfRacers;										//參賽者人數

int speed[100001];										//速度，下标從1開始
int speedNum = 0;										//數組speed不重複資料個數

int tree[100001];										//樹狀數組，下标從1開始

typedef struct node {
	int x, v;											//位置和速度
}Racer;													//參賽者
Racer racer[100001];

void inputRacer() {										//輸入參賽者資訊
	for (int i = 0; i < numberOfRacers; ++i) {
		scanf("%d %d", &racer[i].x, &racer[i].v);		//輸入位置和速度
	}
}

int compareSpeed(const int* a, const int* b) {			//比較函數，速度升序排序
	return (*a) - (*b);
}

int deleteDeduplication() {								//删除重複資料
	int num = 1;										//不重複資料的個數
	for (int i = 2; i <= numberOfRacers; ++i) {
		if (speed[num] != speed[i]) {
			speed[++num] = speed[i];
		}
	}
	return num;											//傳回不重複資料的個數
}

int getSpeedIndex(int key) {							//擷取速度下标，二分查找
	int left, middle, right;
	left = 1;
	right = speedNum;
	while (left <= right) {
		middle = (left + right) / 2;
		if (speed[middle] == key) {						//找到
			return middle;								//傳回下标
		}
		else if (speed[middle] < key) {
			left = middle + 1;
		}
		else if (speed[middle] > key) {
			right = middle - 1;
		}
	}
	return 0;											//未找到，傳回0
}

void discretization() {									//離散化
	for (int i = 0; i < numberOfRacers; ++i) {
		speed[i + 1] = racer[i].v;						//儲存速度
	}
	qsort(speed, numberOfRacers + 1, sizeof(int), compareSpeed);//升序排序
	speedNum = deleteDeduplication();	//去重，并獲得數組speed的不重複資料的個數
	for (int i = 0; i < numberOfRacers; ++i) {
		racer[i].v = getSpeedIndex(racer[i].v);			//擷取新序号（即新速度）
	}
}

int compareRacer(const Racer* a, const Racer* b) {		//參賽者排序
	if (a->x != b->x) {
		return b->x - a->x;								//位置降序
	}
	else if (a->v != b->v) {
		return a->v - b->v;								//速度升序
	}
	return 0;
}

int lowBit(int x) {										//計算2^k的值，
	return x & (-x);									//k是x二進制數末尾0的個數
}

int sum(int n) {										//計算能被超越的人數
	int count = 0;
	while (n > 0) {
		count += tree[n];
		n -= lowBit(n);									//修改為自己的兄弟
	}
	return count;										//傳回被超越的人數
}

void add(int n, int x) {								//将第n個數加x
	while (n <= speedNum) {
		tree[n] += x;
		n += lowBit(n);									//修改為自己的父結點下标
	}
}

long long binaryIndexedTree() {							//樹狀數組操作
	memset(tree, 0, sizeof(tree));						//初始化樹狀數組
	long long ans = 0;									//結果
	for (int i = 0; i < numberOfRacers; ++i) {
		//加上速度比racer[i].v小的人數，也就是第i個人超越的人數
		ans += sum(racer[i].v - 1);
		add(racer[i].v, 1);							//将第i個人加到數組中，數量加1
	}
	return ans;											//傳回最終超越的次數
}

int main() {
	while (EOF != scanf("%d", &numberOfRacers)) {		//輸入參賽人數
		inputRacer();									//輸入參賽者位置和速度
		discretization();								//離散化
		qsort(racer, numberOfRacers, sizeof(Racer), compareRacer);	//排序
		printf("%lld\n", binaryIndexedTree());			//用樹狀數組計算結果
	}
	return 0;
}
           

Java代碼?待補充

其實就是懶?，想要的話就留言吧。

或者等到什麼時候忘了，回來複習再用Java寫吧。。。

版權聲明

1. 轉載、參考、引用必須在首頁添加如下文字：

   [WUSTOJ 1337: Car race game（C）樹狀數組，離散化—wowpH](https://blog.csdn.net/pfdvnah/article/details/94386984)

2. 代碼原創，公開引用不能删除首行注釋（作者，版本号，時間等資訊）；
3. 如果有疑問歡迎評論區留言，盡量解答；
4. 如果有錯誤，還望大俠評論區指正。