有點鼓勵又不太鼓勵,就是微鼓勵。一個人受到微鼓勵後,如果他原本是站著的就會蹲下來,如果原本是蹲著的就會站起來。現在有一堆人排成一排,你可以對其中一個區間的人進行微鼓勵,那一區間的人原本蹲著的就會站起來,原本站著的就會蹲下來。一開始所有人都是站著的,經過幾次為鼓勵之後,問你還有多少人是站著的。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行有一個整數 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