題目鏈接：Bracket Sequencing

---

顯然之和前綴和，和前綴和的min有關(guān)。

如果前綴和大于0，且前綴和的min也大于0，直接放前面最優(yōu)。
如果前綴和大于0，且前綴和的min小于0，所以肯定是先放前綴和的min大的。
如果都小于0，假設(shè)前綴和為a,前綴和的min為b
我們對(duì)于前后兩項(xiàng)可得：b1+a2<a1+b2 -> a1-b1<a2-b2

---

AC代碼：

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e6+10; string str[N]; int n,res; vector<pair<int,int> > v1,v2; inline int ch(char c){if(c=='(') return 1; return -1;} signed main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++){cin>>str[i]; int s=0,mi=1e9;for(int j=0;j<str[i].size();j++) s+=ch(str[i][j]),mi=min(s,mi);if(mi>=0&&s>=0) res+=s;else if(mi<0&&s>=0) v1.push_back({mi,s});else v2.push_back({mi,s});}sort(v1.begin(),v1.end(),[](pair<int,int> a,pair<int,int> b){return a.first>b.first;});for(auto i:v1){if(res+i.first<0) return puts("No"),0;res+=i.second;}sort(v2.begin(),v2.end(),[](pair<int,int> a,pair<int,int> b){return a.first-a.second<b.first-b.second;});for(auto i:v2){if(res+i.first<0) return puts("No"),0;res+=i.second;}puts(res==0?"Yes":"No");return 0; }

總結(jié)

以上是生活随笔為你收集整理的Bracket Sequencing的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。