TIOJ 1176 . Cows

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1176

寫到快瘋掉了.........

由於這題要記錄每一個牛能看到幾個

所以一定要開一個vector去存能看到幾個

於是我一開始寫了這份\(O(n^2)\)的code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,t;

cin>>n;

vector<int> M(n),r(n,0);

vector<bool> stop(n,0);

for(int i=0;i<n;i++)

{

cin>>M[i];

for(int j=0;j<i;j++)

{

if(!stop[j]&&M[i]>=M[j]) r[j]++,stop[j]=1;

else if(!stop[j]) r[j]++;

}

}

for(int i=0;i<n;i++)

cout<<r[i]<<'\n';

}

拿了個82分

看起來還可以

然後仔細想了想該怎麼優化

想到了一個unordered_set+queue的優化

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,t;

cin>>n;

vector<int> M(n),r(n,0);

unordered_set<int> s;

queue<int> q;

for(int i=0;i<n;i++)

{

cin>>M[i];

for(auto e:s)

{

if(M[i]>=M[e]) r[e]++,q.emplace(e);

else r[e]++;

}

while(q.size())

{

s.erase(q.front());

q.pop();

}

s.insert(i);

}

for(int i=0;i<n;i++)

cout<<r[i]<<'\n';

}

因為在上一份code中,無論j的那圈有沒有stop都要跑完\([0,i)\)

用unordered_set就可以讓已stop的牛不會再被跑過

這樣拿下了91分

之後查答案時看到別人都說這題是Monotone queue

維護牛群嚴格遞減的單調性

就可以接近\(O(n)\)的複雜度

(其實我不確定,如有誤歡迎指出)

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,t;

cin>>n>>t;

vector<int> r(n,0);

deque<pair<int,int>> dq;

dq.emplace_back(t,0);

for(int i=1;i<n;i++)

{

cin>>t;

while(dq.size()&&t>=dq.back().first)

{

r[dq.back().second]=i-dq.back().second;

dq.pop_back();

}

dq.emplace_back(t,i);

}

dq.pop_back();

while(dq.size())

{

r[dq.back().second]=n-1-dq.back().second;

dq.pop_back();

}

for(int i=0;i<n;i++)

cout<<r[i]<<'\n';

}