编程介的小学生 2017-07-28 15:30 采纳率: 20.5%
浏览 711
已采纳

Tower

Problem Description
The land price on the MMM island is extremely high. So people on the island all live in a very tall tower with one million floors!! There are N electric service companies (labeled 1 to N) and M power stations on the island. One power station belongs to exactly one company.

At the beginning, the company of each power station is given, and a company can choose one floor to build a power center. Assuming that there are k power stations (on floor a1,a2,...,ak) that belong to a company, and the company chooses floor x to build the power center, the daily cost of this company would be |a1-x|+|a2-x|+...+|ak-x|. MMM, the master of the island, has made a special rule:

x1 <=> x2 <=> x3 <=> ... <=> xn

The operator <=> can be either <= or >=. It means that the power centers chosen by the adjacent companies should follow the specified order. For example, if the rule is x1 <= x2 >= x3, it means that the power center of company 1 should not be higher than that of company 2, and the power center of company 2 should not be lower than that of company 3. Though there is no constraint between company 1 and company 3. If company 1 chooses floor 2 for the power center and company 2 chooses floor 3, the station of company 3 can only be in floor 1, 2 or 3.

Your task is to help the companies calculate their minimum total daily cost.

Input
There are multiple test cases. The first line has an integer T (T ≤ 10), which indicates the number of test cases.

Each test case begins with two integers N and M (1 ≤ N ≤ M ≤ 5*10^5).

There are N - 1 operators on the second line, either '<=' or '>=', separated by spaces, indicating the rules between adjacent companies.

The third line has M pairs of integers. Each pair x_i, y_i describes the i-th power station, where x_i indicates the label of the floor and y_i indicates the label of the company, (1 ≤ x_i ≤ 10^6, 1 ≤ y_i ≤ N). It is guaranteed that each company has at least one power station.

Output
For each test case, output the minimum total daily cost of the island.

Sample Input
3
3 5
<= <=
2 1 3 1 4 2 4 2 5 3
3 8
<= <=
7 3 9 3 3 2 4 2 5 2 6 1 7 1 8 1
4 4
<= >= <=
3 1 1 2 4 3 2 4

Sample Output
1
11
4

  • 写回答

1条回答

  • threenewbee 2017-08-13 15:51
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型