回分類題庫
z075: B.小咲的玩具
關鍵字:

測資點 : 10 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 0 Times / 0 Users | Submit : 48 Times / 11 Users | Accepted rate : 0%
題目加入時間 : 2019-10-04 17:16

Content: 简体中文

小咲是一位可愛天真的少女,她總共擁有K個玩具(玩具以1K編號),並且她把這K 個玩具分成N個群組(群組以1N編號),每個群組至少擁有一個玩具。

小咲對於玩具的喜好程度是不同的,第i個玩具的喜好程度為ci

 在接下來的Q天裡面,第i天小咲會選擇兩個數字Xi,Yi,代表她會從第Xi個群組選擇一 個玩具,第Yi個群組選擇一個玩具,總共兩個玩具來玩。如果她選擇喜好程度為a的玩具和喜好程度為b的玩具,她可以得到min(a,b)的滿足度,min(a,b)代表數字a和數字b中數值比較小的數字。 

身為小咲的朋友,你想要知道,每一天所有小咲可能選擇的組合,滿足度的總和是多少

Sample Input 1為例,第一個群組擁有兩個玩具,滿足度分別為[3,2],第二個群組擁 有一個玩具,滿足度為[4],第三個群組擁有兩個玩具,滿足度分別為[4,7]。第一天,小咲會從第一個群組和第三個群組拿玩具,所有可能的滿足度總和是min(3,4)+min(3,7)+min(2,4)+ min(2,7) = 3 + 3 + 2 + 2 = 10。第二天,小咲會從第三個群組和第二個群組拿玩具,所有可能的滿足度總和是min(4,4) + min(4,7) = 4 + 4 = 8

Input:

輸入的第一行有三個正整數N,K,Q,代表小咲的玩具群組數量,玩具數量,以及小咲玩玩具的天數。

 接下來的K行,每行有兩個正整數Ci,Pi,代表第i個玩具的喜好程度,以及第i個玩具所在的群組編號。

 接下來的Q行,每行有兩個正整數Xi,Yi,代表小咲在第i天要玩的玩具群組。

• 2 N K 150000

1 Q 150000

1 ci 108

1 pi N

1 ≤ Xi,Yi ≤ N,Xi≠Yi

Output:

輸出Q行,第i行輸出一個整數,代表小咲在第i天玩的玩具的所有可能中,滿足度的總和是多少。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3 
5 2 
3 1 
4 3 
2 1 
4 2 
7 3 
1 3 
3 2

Sample Output :

10 8

Hint :

Author :

(管理員:Chang)

  Solve it!   Status Forum