why is my greedy choice wrong? CSES 1084 — Apartments

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2)
5 дней

→ Трансляции

CodeChef Starters 130 Solution Discussion

aryanc403

До начала 17:51:27

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
7	-is-this-fft-	150
9	pajenegod	145
10	BledDest	144

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

why is my greedy choice wrong? CSES 1084 — Apartments

Автор obocheton, история, 4 года назад, По-английски

I was trying this problem CSES 1084.

I greedily choose the lowest sized valid apartment for every applicant (sorted both lists ascendingly).

But it turns out to be a wrong approach.

Why my approach is wrong?

cses

obocheton
4 года назад
15

Комментарии (7)

Показать архивные | Написать комментарий?

AW_Flister

4 года назад, # |

Inserting the apartment sizes into the set may remove some apartments with the same size. Try using a multiset or a regular vector

→ Ответить

CodeSlayer007

4 года назад, # |

← Rev. 3 →

There can be multiple apartments with same size so instead of using set use multiset. And use inbuilt lowerbound function of set as thats faster .And to remove only one element from the multiset use s.erase(it) instead of s.erase(*it) as the later will remove all occurrences of *it.

Spoiler

Your code here...
#include<bits/stdc++.h>
using namespace std;

int a[200005];

int main(){
    int n,m,k,ans=0;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    } 
   sort(a,a+n);
    int aa;
    multiset<int>s;
    for(int i=0;i<m;i++){
        cin>>aa;
        s.insert(aa);
    }

    for(int i=0;i<n;i++){
        int val=a[i]-k;
        auto it = s.lower_bound(val);
        if(it!=s.end() and *it<= a[i]+k){
            s.erase(it);
            ans++;
        }

    }
    cout<<ans<<endl;
    return 0;
}

→ Ответить

AdHocMan

4 года назад, # ^ |

Thanks. I was searching for this one. Your code was helpful for me.

→ Ответить

nisarg_0

3 года назад, # ^ |

I am still getting tle bruh!`

my soln

int solve(int n, int m, int k)
{
    int i,j,ans=0;
    vector<int> applicants(n,0);

    for (auto &it : applicants) cin >> it;
    sort(applicants.begin(),applicants.end()); 

    multiset<int> S;
    for(i=0;i<m;i++)
    {
        int apt;
        cin >> apt;
        S.insert(apt);
    }

    for(i=0;i<n;i++)
    {
        int app = applicants[i];

        auto it = lower_bound(S.begin(),S.end(),app-k);
        
        if(it != S.end() and abs(*it-app) <= k)
        {
            // cout << *it << " ";
            S.erase(it);
            ans++;
        }
    }
    return ans; 
}

Can you help me out?

→ Ответить