Блог пользователя khuda_ka_banda

Автор khuda_ka_banda, 5 лет назад, По-английски

Problem c1 POtions of #723 If i put 4 numbers {2,-2,-1,-1} left code gives ans is 3 and right code gives 2 LEft code

int n;
    cin >> n;
    ll arr[n];
    set<pair<ll, int>> s1;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        s1.insert({arr[i], i});
        if (sum < 0)
        {
            pair<ll, int> p = *s1.begin();
            sum -= p.ff;
            s1.erase(p);
        }
    }
    cout << size(s1) << newline;

Right code

int n;
    cin >> n;
    ll arr[n];
    set<int> s1;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        s1.insert(arr[i]);
        if (sum < 0)
        {

            sum -= *s1.begin();
            s1.erase(s1.begin());
        }
    }
    cout << sz(s1) << nline;
  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Set does not take duplicate elements so when you are using pair all elements are unique because of their indexes but when you are just using set duplicate elements are not there in the set therefore result is different