투표

*lower_bound로 현재 심사기준에 맞는 경기 비용의 경계 인덱스를 구하고(이 경기가 가장 재미있는 경기는 아닐 수도 있다.)

입력받은 순서가 적은 순서가 더 재미있는 경기이기 때문에 이 비용을 넘지 않는 경기들을 살펴보면서 가장 재미있는 경기에 투표할 수 있도록 한다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pp;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    vector<pp> games;
    for (int i = 0; i < n; i++)
    {
        //재미있는 순서대로 개최 비용이 주어진다.
        int a;
        cin >> a;
        games.push_back(pp(a, i));
    }
 
    stable_sort(games.begin(), games.end()); //개최비용이 작은 순서대로 정렬
 
    int vote[1001] = {0};
    for (int i = 0; i < m; i++)
    {
        int tmp;
        cin >> tmp;
 
        //tmp를 넘지 않는 개최비용 중 가장 재밌는 경기에 투표
        vector<pp>::iterator it = lower_bound(games.begin(), games.end(), pp(tmp, 0));
 
        //비용을 넘지 않는 경기 중 가장 재미있는 경기를 찾는다.
        int idx = it - games.begin();
        if (it->first > tmp)
            idx--;
 
        if (idx == 0)
            vote[0]++;
        else
        {
            int minN = games[idx].second;
 
            for (int j = 0; j < idx; j++)
            {
                //비슷한 비용이면 더 재밌는 순서가 앞에 위치해있다.
                if (games[j].second < minN)
                {
                    minN = games[j].second;
                }
            }
            vote[minN]++;
        }
    }
 
    int maxIdx = 0, max = 0;
    for (int i = 0; i < n; i++)
    {
        if (vote[i] > max)
        {
            max = vote[i];
            maxIdx = i;
        }
    }
 
    cout << maxIdx + 1 << '\n';
    return 0;
}