題目連結: https://zerojudge.tw/ShowProblem?problemid=b844
# 內容
給你一堆按鈕 (編號從 1 開始)，每個按鈕旁邊的數字都顯示為 0，按下第 K 個按鈕可以把第 K 個以後的數字 1 變 0，0 變 1 (包括第 K 個)，讓你按下按鈕 N 次之後，有 Q 個詢問，問第 P 個數字為 0 還 1?
# 解題思路
直觀解陣列會太大，且會 TLE (O (N*K) )。
用陣列記錄 N 個按鍵號碼，陣列中有幾個數字小於等於詢問的數字，即 0、1 切換的次數
可先排序，以 2 分搜加速
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int N,Q; | |
while(cin>>N>>Q){ | |
vector <int> K(N); | |
for(int i=0;i<N;i++) | |
cin>>K[i]; | |
sort(K.begin(),K.end()); | |
for(int i=0,t;i<Q;i++){ | |
cin>>t; | |
vector<int>::iterator it; | |
it=upper_bound(K.begin(),K.end(),t); | |
cout<<((it-K.begin())%2?"1\n":"0\n"); | |
} | |
} | |
return 0; | |
} |
