Найти минимальный баланс на мобильном телефоне

Question

У Алисы есть родственники N. Она будет говорить с соответствующим родственником точно за T [i] минуты. Каждая минута стоит 1 доллар. Тем не менее, ее родственники после разговора добавили пополнения X [i] долларов в свой мобильный телефон. Первоначально у нее есть баланс в долларах США на мобильном телефоне.

Нам нужно найти минимальное значение M, которое она должна иметь на своем телефоне, чтобы она не выходила из равновесия во время любого вызова (встречный отрицательный баланс).

Примечание: Алиса может позвонить родственникам в любом порядке. Каждый родственник будет называться ровно один раз.

Пример: Пусть N = 2 и пара T [I] Х [I] для каждого из двух относительно выглядит следующим образом:

1 1 
2 1 

Тогда здесь ответ будет 2.

В настоящее время 1 ≤ N, X, T ≤ 10^5. Так что лучший способ найти минимальное значение решения M. Brute не получится, поэтому мне нужен подход O (N) или O (N * logN)

Answer 1

Мы сохраняем разницу между стоимостью звонка и пополнения количество.

Затем мы поддерживаем два массива/векторы. Если наша сумма подзарядки строго больше стоимости звонка, мы ставим вызов в первом массиве, иначе мы помещаем его во второй массив.

Затем мы можем сортировать первый массив в соответствии со стоимостью и вторым массивом в зависимости от суммы пополнения. Затем мы обновляем диф, добавив наималейшее количество Маны от вызова, где наши расходы больше, чем пополнение

Тогда мы можем перебирать наш первый массив и обновлять наше максимум требование, требование для каждого вызова и текущего баланса. Наконец, наш ответ будет максимальным между максимальным требованием и поддерживаемой нами разностью.

Пример: -

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

Наш первый массив не содержит в себе ничего, как все звонки стоили больше, чем или равное количество перезарядить. Итак, мы помещаем оба вызова в наш второй массив. . Разница обновляется до 2, прежде чем мы отсортируем массив. Затем добавим перезарядку min , которую мы можем получить от звонков на наш diff (т.е. 1). Теперь diff стоит в 3. Затем, когда наш первый массив не содержит элементов, наш ответ равен diff ie 3 .

Время Сложность: - O (п)

Рабочий пример: -

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