A.Stas and the Queue at the Buffet
题目描述:
During a break in the buffet of the scientific lyceum of the Kingdom of Kremland, there was formed a queue ofnnhigh school students numbered from11tonn. Initially, each studentiiis on positionii. Each studentiiis characterized by two numbers—aiaiandbibi.Dissatisfactionof the personiiequals the product ofaiaiby the number of people standing to the left of his position, add the productbibiby the number of people standing to the right of his position. Formally, thedissatisfactionof the studentii, which is on the positionjj, equalsai⋅(j−1)+bi⋅(n−j)ai⋅(j−1)+bi⋅(n−j).
The director entrusted Stas with the task: rearrange the people in the queue so thatminimize the totaldissatisfaction.
Although Stas is able to solve such problems, this was not given to him. He turned for help to you.
输入描述:
The first line contains a single integernn(1≤n≤1051≤n≤105)— the number of people in the queue.
Each of the followingnnlines contains two integersaiaiandbibi(1≤ai,bi≤1081≤ai,bi≤108)— the characteristic of the studentii, initially on the positionii.
输出描述:
Output one integer—minimum totaldissatisfactionwhich can be achieved by rearranging people in the queue.
测试样例:
样例输入 1
Copy
3
4 2
2 3
6 1
样例输出 1
Copy
12
样例输入 2
Copy
4
2 4
3 3
7 1
2 3
样例输出 2
Copy
25
样例输入 3
Copy
10
5 10
12 4
31 45
20 55
30 17
29 30
41 32
7 1
5 5
3 15
样例输出 3
Copy
1423
提示:
In the first example it is optimal to put people in this order: (3,1,23,1,2). The first person is in the position of22, then hisdissatisfactionwill be equal to4⋅1+2⋅1=64⋅1+2⋅1=6. The second person is in the position of33, hisdissatisfactionwill be equal to2⋅2+3⋅0=42⋅2+3⋅0=4. The third person is in the position of11, hisdissatisfactionwill be equal to6⋅0+1⋅2=26⋅0+1⋅2=2. The totaldissatisfactionwill be1212.
In the second example, you need to put people in this order: (3,2,4,13,2,4,1). The totaldissatisfactionwill be2525.
n = int(input()) # 读入nclass xx:def __init__(self):self.x = 0self.y = 0self.z = 0from functools import cmp_to_key # 引入模块def cmp1(a, b):if a.z>b.z:return -1else:if a.z==b.z and a.y<b.y:return -1return 1list1 = [] for i in range(0, n):list1.append(xx())list1[i].x, list1[i].y,= map(int,input().split())list1[i].z=list1[i].x-list1[i].ylist1.sort(key=cmp_to_key(cmp1)) # 按照cmp来排序sum=0for i in range(0, n):sum+=list1[i].x*i+list1[i].y*(n-i-1)print(sum)
