算法比賽模拟題精解之“Tairitsu and Dynamic Objects”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第114題：Tairitsu and Dynamic Objects 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：貪心

檢視題目：Tairitsu and Dynamic Objects

Hikari 和 Tairitsu 面前有n個物品，這些物品編号為1,2,...,n。

每個物品有兩個屬性。第 i 個物品的兩個屬性分别為ai, bi 。

初始 n 個物品均可被選取。Hikari 與 Tairitsu 會輪流選取目前可選取的物品中的一個，并把它拿走，這個物品之後不可被選取。第一輪 Hikari 先選取。

設 Hikari 選取的物品編号的集合為H ，Tairitsu 選取的物品編号的集合為T 。

所有物品均被選取完之後，Hikari 得分為∑ai(i∈H) ；而 Tairitsu 得分為 ∑bi(i∈T) 。

Hikari 和 Tairitsu 都希望自己的得分比對方大，你需要求出雙方都使用最優政策的情況下，雙方各會獲得多少分。

注意：若對于某個人來說，剩餘的物品中有多個對兩人分數大小關系影響相同的物品，那麼他會優先選擇bi 最大的那個。

輸入一個正整數n，表示物品個數。

再輸入兩個數組a和b，分别表示n個物品的A屬性和n個物品的B屬性。（保證1<=n<=2*1e5, 0<=ai,bi<=1e9）

輸出一行，兩個整數分别表示Hikari和Tairitsu的得分。

示例1

輸入：

5

[1,2,3,4,5]

[5,4,3,2,1]

輸出：

[9,6]

解題思路：

根據題意，分析得知，Hikari 和 Tairitsu 每次會優先選擇 ai+bi 的值最大的物品，當物品的 ai+bi 值相等時，選擇bi大的那個。

是以，可以對物品進行排序，排序有兩個依據，優先依據 ai+bi 的值，然後是bi的值。降序排好後，Hikari 和 Tairitsu 依次按順序選擇物品，Hikari先選擇，選擇好以後，分别計算Hikari 和 Tairitsu 的分數即可。

時間複雜度：O(n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>