题意:日本东海岸有N个城市(从北到南命名为1, 2, ..., N),西海岸有M个城市(从北到南命名为1, 2, ..., M),东西之间有K条高速公路,问这K条高速公路有多少个交叉点(一个交叉点有且只有两条高速公路经过)(1000 <= N, M <= 1000)。
题目链接:http://poj.org/problem?id=3067
——>>好题。。。#^_^
先将东岸城市从北到南排序,再将西岸城市从北到南排序;接着从北到南遍历西岸城市,设a[i]表示西岸城市i南部的所有城市目前出现的次数,那么此时西岸城市i产生的交点数为a[i],设sum[i]表示西岸前i个城市此时出现次......
阅读全文