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?
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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?
Name |
---|
Inserting the apartment sizes into the set may remove some apartments with the same size. Try using a multiset or a regular vector
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.
Thanks. I was searching for this one. Your code was helpful for me.
I am still getting tle bruh!`
Can you help me out?
same doubt
Because in set or multi_set the lower_boud syntax is different from the normal vector and syntax will be set.lower_bound(val);
Same solution But get tle . So, much tight bounds in simple problem . https://cses.fi/paste/f28396ef9920770e4c50e2/