#53638: 一個0.1s想法
petercoding522@gmail.com
(peter)
因為要越來越大
所以排序
然後用迴圈交錯找兩次(因為起始顏色不同)
0.1s
ps. 如同有人提到的所以用push_back
c++ 程式碼
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int t;
cin >> t;
while (t--)
{
vector<int> bl({}),re({});
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int p;
cin >> p;
if( p>=0 ) bl.push_back(p);
else re.push_back(-p);
}
sort(bl.begin(),bl.end());
sort(re.begin(),re.end());
int cnt = 0,cnt2 = 0;
int tmp = 0;
for (int i = 0,j = 0; i < bl.size(); i++)
{
if( bl[i]<=tmp ) continue;
tmp = bl[i];
++cnt;
while( j<re.size() && re[j] <= tmp ){
++j;
}
if( j>=re.size() ) break;
tmp = re[j];
++cnt;
}
tmp = 0;
for (int i = 0,j = 0; i < re.size(); i++)
{
if( re[i]<=tmp ) continue;
tmp = re[i];
++cnt2;
while( j<bl.size() && bl[j] <= tmp ){
++j;
}
if( j>=bl.size() ) break;
tmp = bl[j];
++cnt2;
}
cout<<max(cnt,cnt2)<<'\n';
}
return 0;
}