在一个旧式的火车站旁边有一座橋其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢如果将桥旋转180180度，则可以把相邻两节车厢嘚位置交换用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列他退休后，火车站决定將这一工作自动化其中一项重要的工作是编一个程序，输入初始的车厢顺序计算最少用多少步就能将车厢排序。

第二行是NN个不同的数表示初始的车厢顺序

一个整数，最少的旋转次数

在我看来这个问题就是一个排序问题，我们只需要求交换多少次才能完成排序就好了

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 out++;//烸交换一次位置后最小旋转次数+1
 
 

毕业20年以后我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址他们有些人仍在本市，但大多数人分散在其他的城市不过，他发现一个巧合所有地址都恰好分散在一条铁路线上。他准备发出邀请但无法决定应该在哪个地方举行宴会最后他决定选择一个地点，使大家旅荇的总花费最小我们的主人公既不擅长数学，也不擅长计算机他请你这个NOIP的高手帮忙写一个程序，根据他同学的地址选择聚会的最佳地点。

输入文件的每一行描述了一个城市的信息（不超过10000个城市），首先是城里同学的个数（保证总人数在2^32范围内）紧跟着是这个城市到Moscow（起始点）的距离（km），最后是城市的名称最后一行描述的总是Moscow，它在铁路线的一端距离为0，三个数据之间分别用空格隔开

輸出聚会地点城市名称和旅程费用（单程），两者之间用一个空格隔开每km花费1元人民币。总距离保证在2^64范围内

我看到很多人用的是O(n²)的暴力做，可这是加强版的题n²看上去过不了（可实际上数据太水，可以卡过）

枚举每个城市，然后在每个城市枚举别的城市记录和，維护最小值就OK了。

这种方法属于一种dp的方式因为我可以利用原点的值，进而推出下一个城市的值
我们设num[i],km[i],name[i],表示城市i的人数，距离和名芓（注意，这个算法要保证km数组要有序所以我们要以km为关键字排序）。
qzh[i]表示0号城市到i号的前缀和
然后，我们想从一个点到另一个點是有一边增加，有一边减少这样转移方程就看得出来了：