Решение задачи Лалаландия и яблони с Codeforces

Без пояснения   Просмотров: 1019

Amr живет в Лалаландии. Лалаландия — очень красивая страна, расположенная на координатной прямой. Лалаландия славится своими яблонями — в стране они растут везде.

Всего в Лалаландии ровно n яблонь. Яблоня номер i расположена в точке x i, на ней растет a i яблок. Amr хочет собрать яблоки с этих яблонь. Amr сейчас стоит в точке x = 0. Сначала он выбирает, вправо ли он пойдёт или влево. Он будет следовать в этом направлении, пока не дойдет до первой яблони. Он соберет с этой яблони все яблоки, а затем пойдет в противоположном направлении и будет идти, пока не дойдет до первой непосещённой яблони, снова развернётся, и так далее. Иными словами, посещая каждую новую яблоню, Amr разворачивается и идёт в противоположном направлении. Amr перестанет собирать яблоки, когда в направлении его движения не останется ни одной непосещённой яблони.

Какое максимальное количество яблок он сможет собрать?

Код 

#include <bits/stdc++.h>

using namespace std;

typedef pair <int,int> pii;

int main()
{
    int n;  cin >> n;

    vector <vector <pii>> a(2);

    for(int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x > 0].emplace_back(abs(x), y);
    }

    sort(a[0].begin(), a[0].end());
    sort(a[1].begin(), a[1].end());

    int m = min(a[0].size(), a[1].size()) + 1;

    int Ans = 0;

    for(int i = 0; i < m && i < a[0].size(); i++)   Ans += a[0][i].second;
    for(int i = 0; i < m && i < a[1].size(); i++)   Ans += a[1][i].second;

    cout << Ans << endl;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp