查找手机最低余额 [英] Find minimum balance in mobile

问题描述

爱丽丝有N个亲戚。她会跟第i个相对的正是T [I]分钟。每分钟的花费她1美元。然而，她的亲戚交谈后，加入的X [I]美元补给她的移动。最初，她有米不等平衡在她的手机。

Alice have N relatives. She will talk to ith relative for exactly T[i] minutes. Each minute costs her 1 dollar . However, her relatives after the conversation, add a recharge of X[i] dollars in her mobile. Initially, she have M dollars balance in her mobile phone.

我们需要找到M的最小值，她必须首先在她的电话，让她在任何呼叫没有用完的余额（遇到负平衡）。

We need to find the minimum value of M, that she must have initially, in her phone, so that she don't run out of balance during any of the call (encounter negative balance).

注意：爱丽丝可以以任意顺序调用的亲戚。每个相对会完全调用一次。

实施例：设N = 2和一对T [i]于X [i]于每对相对的是如下：

Example : Let N=2 and pair T[i] X[i] for each of the two relative is as follow:

1 1
2 1

那么这里的答案是2。

Then here answer is 2.

现在1≤N，X，T≤10 ^ 5。那么有什么方法可以找到M.蛮力解决方案的最小值将不工作了，所以我想一些O（N），或最好的办法O（N * logN）的方法

Now 1 ≤ N,X,T ≤ 10^5 . So what can be best way to find the minimum value of M. Brute solution won't work out so I want some O(N) or O(N*logN) approach

推荐答案

我们保持通话费用之间的差额   和充值金额。

We maintain the difference between call cost and recharge amount.

然后，我们维持两个数组/向量。   如果我们的充值金额是严格小于通话费用较大，我们把   第一个阵列中的呼叫，否则我们就把它的第二个数组

Then we maintain two arrays/vectors. If our recharge amount is strictly greater than cost of call, we put the call in the first array ,else we put it in the second array.

然后，我们可以根据成本和第二阵列排序第一阵列   根据充值金额。然后，我们通过添加更新的差异   最少从通话充值其中，我们的成本是大于补给

Then we can sort the first array according to the cost and the second array according to the recharge amount. We then update the diff by adding the least amount of recharge from the call where our cost is greater than recharge

然后，我们可以通过我们的第一个数组遍历和更新我们的最大   要求，每个呼叫和电流balance.Finally，我们的答案要求   将是最大的要求，我们一直保持着差异的最大值。

Then we can iterate through our first array and update our max requirement,requirement for each call and current balance.Finally, our answer will be the maximum between max requirement and the diff we have maintained.

示例： -

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

我们的第一个数组包含什么，因为所有的电话都花费大于    或等于充电量。所以，我们把我们的第二个数组两个通话    该差异被更新为2之前，我们对该数组进行排序。然后，我们添加分钟    充值就可以从电话到我们的差异（即1）。现在，该差异看台获得    在3.Then作为我们的第一个数组包含元素，我们的答案是等于    的差异即3。

Our first array contains nothing as all the calls have cost greater than or equal to recharge amount. So, we place both calls in our second array The diff gets updated to 2 before we sort the array. Then, we add the min recharge we can get from the calls to our diff(i.e 1).Now, the diff stands at 3.Then as our first array contains no elements, our answer is equal to the diff i.e 3.

时间复杂度： - 为O（n）

工作实例： -

#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;
}

这篇关于查找手机最低余额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！