ZeroJudge B526: 先別管這個了，你聽過微鼓勵嗎？

有點鼓勵又不太鼓勵，就是微鼓勵。一個人受到微鼓勵後，如果他原本是站著的就會蹲下來，如果原本是蹲著的就會站起來。現在有一堆人排成一排，你可以對其中一個區間的人進行微鼓勵，那一區間的人原本蹲著的就會站起來，原本站著的就會蹲下來。一開始所有人都是站著的，經過幾次為鼓勵之後，問你還有多少人是站著的。

範例測資

範例輸入範例輸出
第一行有一個整數 N (N <= 2,000,000,000)，代表有 N 個人由左至右排成一排，由最左邊的人開始編號分別為 1, 2, 3, …, N。
第二行有一整數 M (M <= 100000)，接下來會有 M 次微鼓勵。
接下來 M 行每行有兩個整數 Li 和 Ri。表示對 Li 至 Ri 這閉區間 (包含兩端) 的人作微鼓勵。		請輸出最後有多少人站著。
5
3
1 3
3 5
1 5		4

解題思路

使用 Map 來存每一次微鼓勵的範圍，因為只要微鼓勵兩次就會變成站著等於沒有微鼓勵。

將 R+1 之後就可以知道 R-L 是被微鼓勵的人數，將 L 和 R 放到 Map 中，如果已經有資料了就代表有重複微鼓勵的情況，所以將已經出現過的Map值做刪除，然後沒有存過的資料存到Map中。

最後將 Map 轉換為 Vector<Pair<int, int>> 然後兩兩一組進行 R-L 的動作並將答案相加即可。

範例程式碼－ZeroJudge B526: 先別管這個了，你聽過微鼓勵嗎？

#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<int, int>MAP;

void change(int N)
{
    if (MAP[N] == 0)
    {
        MAP[N]++;
        return;
    }
    MAP.erase(N);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i<M; i++)
    {
        int a, b;
        cin >> a >> b;
        b++;
        change(a);
        change(b);
    }
    vector<pair<int, int>>ans;
    copy(MAP.begin(), MAP.end(), back_inserter(ans));
    int sum = 0;
    for (int i = 0; i<ans.size(); i++)
    {
        sum += ans[i+1].first - ans[i].first;
        i++;
    }
    cout << N-sum << "\n";
}

//ZeroJudge B526
//Dr. SeanXD
標籤

相關文章

發佈留言