如何找到M的最小值？

Question

我試圖解決這個問題：

你有N個親戚。你會和第i位親屬交談，確切的時間是分鐘。每分鐘花費你1美元。談話結束後，他們將在您的手機中添加Xi元的充值。最初，您的手機中有 的M美元餘額。

找到M的最小值，即你必須首先在你的 手機，讓你不失去平衡的過程中的任何通話 的運行（遇到負平衡）。

注意：您可以以任何順序呼叫親屬。每個親戚只需撥打 一次。

輸入：

N 
T1 X1 
T2 X2 

2 
1 1 
2 1 

輸出：

2 

這看起來很容易對我來說是第一次，但我沒能找到確切的解決方案。

我最初的想法：

我們沒有任何問題，在Xi > Ti因爲它不會降低我們的初始 平衡。我們需要注意的情況下，我們將運行 損失，即Ti > Xi。 但我無法表達，這將導致最小值爲 的初始值。

需要指導解決此問題以找到最佳解決方案。

Answer 1

更新： -

二進制搜索方法似乎導致了錯誤的結果（由用戶greybeard在下面的評論中提供的 測試用例作爲證明

所以，這是另一種方法。我們維持通話費用 與充值金額之間的差額

然後我們維護兩個數組/向量 如果我們的充值金額嚴格大於通話費用，我們將 第一個數組中的調用，否則我們把它放在第二個數組中。

然後我們可以根據成本和第二個數組 根據再充值量對第一個數組進行排序。然後，我們通過在呼叫中添加最少數量的再充值來更新差異，其中我們的成本高於充值

然後我們可以遍歷我們的第一個數組並更新我們的最大需求，每個呼叫的需求和當前餘額。最後，我們的回答 將是最大需求和我們維護的差異之間的最大值。

實施例： -

N = 2 
    T1 = 1 R1 = 1 
    T2 = 2 R2 = 1 

我們的第一個數組包含毫無作爲所有的呼叫花費大於 或等於充電量。因此，我們將這兩個調用放在第二個數組中 在我們對數組進行排序之前，diff將更新爲2。然後，我們添加我們可以從我們的差異（即1）的調用中獲得的充值。現在，差異代表 在3。然後，因爲我們的第一個數組不包含元素，我們的答案等於 差異即3 。

時間複雜度： - O（nlogn）

工作實例： -

#include<bits/stdc++.h> 
using namespace std; 
#define MAXN 100007 

int n,diff; 
vector<pair<int,int> > v1,v2; 

int main(){ 
    diff = 0; 
    cin>>n; 
    for(int i=0;i<n;i++){ 
    int cost,recharge; 
    cin>>cost>>recharge; 
    if(recharge > cost){ 
     v1.push_back(make_pair(cost,recharge)); 
    }else{ 
     v2.push_back(make_pair(recharge,cost)); 
    } 
    diff += (cost-recharge); 
    } 
    sort(v1.begin(), v1.end()); 
    sort(v2.begin(), v2.end()); 
    if(v2.size() > 0)diff += v2[0].first; 
    int max_req = diff, req = 0,cur = 0; 
    for(int i=0; i<v1.size(); i++){ 
     req = v1[i].first - cur; 
     max_req = max(max_req, req); 
     cur += v1[i].second-v1[i].first; 
    } 
    cout<<max(max_req,diff)<<endl; 
    return 0; 
} 

Answer 2

（這是一個wiki帖子：你是邀請編輯，不需要太多聲望就可以這樣做）
高效工作意味着完成手頭的任務，不需要付出過多的努力。在此方面：

• 的OP詢問guidance in approaching this problem to find optimal solution - 不的（如在此entirely similar, older question一樣）。
• 問題陳述要求the minimum value of M - 不是呼叫的最佳順序或如何找到它。

要找到最初所需的最低餘額，分類親戚/（T，X）-pairs /電話（順序威力有一個意思，如果不是問題，因爲說明）

1. T < X讓XT更多，以便跟隨呼叫。爲了增加成本。
   開始假設初始餘額爲1.對於每次通話，如果您可以負擔得起，減去其成本，增加其退款並對其進行會計處理。如果你負擔不起（暫時），把它擱置/暫時擱置/放在優先隊列中。在「獎勵電話」結束時，依次移除隊列中的每一個隊長，考慮到初始平衡的必然增加。
   此部分以的最高平衡結束，但是。
2. T = X對其他呼叫沒有影響。只要以最高的平衡，以任何順序。
   整個順序所需的最高餘額不能低於任何單個呼叫的成本，包括這些。
3. T> X爲後續調用留下T-X。按順序退款。
   （作爲任何電話，這可能在退款前達到零的餘額 由於電話訂單不會改變總成本，所以要求最小初始餘額的訂單將是那些產生最低最終餘額的訂單。這個類別所需的平衡，不要忘記最少的退款。）

結合所有類別的要求。
請記住要求指導。