[アルゴリズム]Algospot NERD 2

11196 ワード
algospot algorithm tree テキストリンク
ソース:https://algospot.com/judge/problem/read/NERD2

質問する


空前の盛況を誇った前回のAlgospot年度模擬試験の後、プログラミング大会の情熱は日増しに高まり、今年は10万人以上が応募する見通しだ.しかし、採点官のボランティアは例年のように5人しかいないので、彼らを試合に参加させることはできない.そのため、今年は参加申請を受けた人の中で本当のプログラマーだけが試合に参加できることにしました.
ジョンマンの新しい理論によると、ある人のナード指数は以下の2つの値によって決定される.
algospotオンラインスコアリングシステムで解決された問題数p
夜更かしして今まで食べたラーメンの数q
この理論によれば、ある参加者aの問題数paと誤り数qaをそれぞれ別の参加者bの問題数pbと誤り数qbと比較すると、pa一人が参加できるかどうかは他の人が決めるので、新しい人が参加を申し込むたびに参加人数が変わります.たとえば、次の4人が順次参加を申請するとします.
참가자	종만 	재훈	효승	광규
문제 수	 72	57	74	64
라면 그릇 수50	67	55	60
鐘万と在勲が順番に試合に参加することを申し込めば、試合に参加できる人数はそれぞれ1、2に増えるが、孝勝に問題があれば茶碗数も鐘万より多いので、孝勝が試合に参加することを申し込むと鐘万は試合に参加できなくなる.そのため、この4人が参加を申請するたびに、参加できる人数は1、2、2、3になります.
このように、一人一人が試合に応募すると、参加人数の変化を計算するプログラムを作成することができます.

入力


入力された最初の行は、テストケースの数C(1<=C<=50)を与える.各テストケースの最初の行では、参加者の数はN(1<=N<=50000)であった.そして、N行において、2個の整数毎に、各人の質問数piとカップラーメン数qiが参加を申請する順番で与えられる(0<=pi,qi<=10000).二人の質問数とラーメンの数が同じではない場合を想定することができます.
入力量が多いので、クイック入力関数を使用することをお勧めします.

しゅつりょく


各人が試合に応募するたびに参加資格数を計算し、各テストケースに合計数を出力します.

正しいコード

#include <bits/stdc++.h>
#define FASTio ios_base ::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

map<int, int> coords;

bool isDominated(int x, int y)
{

    map<int, int>::iterator it = coords.lower_bound(x);

    if (it == coords.end())
        return false;


    return y < it->second;
}
void removeDominated(int x, int y)
{
    map<int, int>::iterator it = coords.lower_bound(x);

    if (it == coords.begin())
        return;
    --it;

    while (true)
    {


        if (it->second > y)
            break;

        if (it == coords.begin())
        {
            coords.erase(it);
            break;
        }

        else
        {
            map<int, int>::iterator jt = it;
            --jt;
            coords.erase(it);
            it = jt;
        }
    }
}


int registered(int x, int y)
{

    if (isDominated(x, y))
        return coords.size();
    
    removeDominated(x, y);
    coords[x] = y;
    return coords.size();
}

int main()
{
    int c;
    cin >> c;
    while (c--)
    {
        int n;

        cin >> n;

        int ans = 0;

        while (n--)
        {
            int p, q;

            cin >> p >> q;

            ans += registered(p, q);
        }
        cout << ans << endl;
    }
    return 0;
}

解答と思考過程


問題が分からないのでうろうろしている.
初めてmapを使いましたが、コードもよく分からなかったので調べて勉強しました.
問題をどのように解決すべきかの観点がわかりますが、コードで実現するには限界があります...
AWSのS3上に静的なWebサイトを公開して、「Hello World」を表示するまでの全手順
あなたのHTMLのレベルにトリック?