FOJ 1021 飞船赛

一，题目描述

      题目地址：  http://acm.fzu.edu.cn/problem.php?pid=1021

 

二，题目分析

1.暴力**：根据题目给定的超车含义，由于在0秒内即可加速到最大速度，那么只要位于后面的飞船的速度大于前面的飞船速度，即可发生超车现象。由于暴力**时间复杂度过高，提交显示超时

2.由于最大速度为100，故开辟一个大小为101空间speeds记录最大速度的飞船数量,每次录入一个飞船信息，实时更新。

speeds[i] :表示当前速度为 i 的飞船，由题意可知，给定的非常位置是递增的，所以每次录入一个飞船的信息，对应的速度飞船数量加1，并且发生超车的次数就是已经录入speed数组中速度大于该飞船的数量。

三，代码解答

#include<vector>
#include<cstdio>
#include<iostream>
using namespace std;


 
int main() {
	int n;			//飞船数量
	int pos, speed;
	while (cin >> n) {
		vector<int> speeds(101, 0);
		int count = 0;				//发生超车的次数
		for (int i = 0; i < n; i++) {
			cin >> pos >> speed;			//输入每个的位置 ，速度
			speeds[speed]++;
			for (int j = speed+1; j <= 100; j++) {
				count = count + speeds[j];
				count %= 1000000;		//取模运算
		    }
		}
		cout << count << endl;
	}
	return 0;
}