Решение задачи Семечки с Меньшиков

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


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

Перед тем как выйти на рынок в качестве ещё одного продавца семечек, Вы провели исследование рынка, чтобы найти зависимость числа покупателей от двух названных факторов. Исследование показывает, что большинство покупателей следуют одному и тому же шаблону. Они проходят мимо нескольких мест, замечая и запоминая цены, а затем после обхода K мест, возвращаются к месту с наименьшей замеченной ценой, совершают там покупку, затем покидают базар. Если есть несколько мест с одинаковой ценой, покупатель выбирает ближайшее.

Предположим, что есть пять мест с ценами 37, 34, 34, 35, 33. Если покупатель с K = 4 идёт слева направо, он видит семечки по ценам 37, 34, 34, 35. В этот момент он решает, что видел достаточно, возвращается к третьему месту и покупает семечки там. Хотя на втором месте цена та же, что и на третьем, покупателю до него идти дальше. Если бы тот же покупатель зашёл справа, он бы увидел цены 33, 35, 34, 34, затем остановился и вернулся бы к пятому месту.

Число мест, пройденных до принятия решения (K), является функцией жадности и терпеливости покупателя, и, очевидно, различается у разных покупателей. Исследование выявило средний процент BK покупателей для всех значений K (1 <= K <= N, 0 <= BK <= 99, сумма всех BK равна 100).

Вам следует определить оптимальную стратегию на этом рынке (то есть цену и положение нового места, которое максимизирует ожидаемый средний доход) в предположении, что половина клиентов идёт в направлении от первого места к N-му, а другая половина - от N-го места к первому, и они следуют описанному шаблону.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> Pr,B,posPr,PrRev;
int maxP = -1, resL = -1, resP = -1;
void input()
{
    cin>>n;
    Pr.resize(n); B.resize(n);
    for (int i=0;i<n;i++) {
        cin>>Pr[i];
        posPr.push_back(Pr[i]);
        posPr.push_back(Pr[i]-1);
    }
    for (int i=0;i<n;i++)
        cin>>B[i];
}
int calc(int L, int P, vector<int> &Pr) {
    int curB = 0;
    // идем слева
    bool isLeft = true;
    for (int i=0; i <= L;i++) {
        if (Pr[i]<P)
            isLeft = false;
    }
    if (isLeft) {
        int ML = n-1;
        for (int i=L+1;i<n-1;i++) {
            if (Pr[i] <= P) {
                ML = i;
                break;
            }
        }
        for (int i=L+1; i<=ML; i++)
            curB += B[i];               
    }
    return curB;
}
void solve()
{
    sort(posPr.begin(),posPr.end());
    vector<int>::iterator it = unique(posPr.begin(),posPr.end());
    posPr.resize( it - posPr.begin());
    PrRev = Pr;
    reverse(PrRev.begin(),PrRev.end());
    for (int L=0; L<=n-2; L++) {
        for (vector<int>::iterator P = posPr.begin(); P != posPr.end(); P++) {
            int f = calc(L, *P,Pr);
 
            int s = calc(n-2-L, *P,PrRev);
 
            int curB = f+s;
 
            int curP = curB * *P;
            if (curP > maxP) {
                maxP = curP;
                resP = *P;
                resL = L;
            }
        }
    }
    cout<<resL+1<<' '<<resP;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

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



Комментарии

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