我们都知道最构造方案是啥 但要注意的是众数不能超过n/2这个条件 要是跨越了n/2这个线 就要取到等于号 所以要想等于n/2并且合法 就必须得 是最小值或者最大值
#include <bits/stdc++.h> using namespace std; const int N = 1e4+10; const int M = 1<<10; const int mod = 1e9+7; #define int long long #define endl '\n' #define Endl '\n' #define yes cout<<"YES"<<endl; #define no cout<<"NO"<<endl; #define _ 0 #define inf 0x3f3f3f3f3f3f3f3f #define fast ios::sync_with_stdio(false);cin.tie(nullptr); signed main(){ fast int T;cin>>T; while(T--){ int n;cin>>n; vector<int>a(n); map<int,int>mp; int flag=0,flag1=0; int cnt=-1; for(int i=0;i<n;i++){ cin>>a[i]; mp[a[i]]++; if(mp[a[i]]>n/2){ flag=1; }else if(mp[a[i]]==n/2){ flag1++; cnt=a[i]; } } if(n%2||flag){ no goto out; } if(flag1==1){ sort(a.begin(),a.end()); if(a[0]==cnt||a[n-1]==cnt); else { no goto out; } } yes sort(a.begin(),a.end()); for(int i=0,j=n/2;j<n;j++,i++){ cout<<a[i]<<' '<<a[j]<<' '; } cout<<endl; out:1; } return ~~(0^_^0); }
讲一下思路吧 我们可以直接特判掉AB数目不合法的 然后我们任务就是把剩余的cntAB cntBA 合法的安排上
怎么做呢 其实就是一个贪心 我们先把cnt少的安排上去 并且尽可能的安排的地方是 比如AB AABB里的AB 我们可以排序把每个重要级 然后如果实在没办法 就只好安排到 ABA这种里面 但是这也不会引起连锁反应
也就是说 我们至少也要破坏一个BA 最后check 是否有足够多的BA即可
这道题 思维难度 真大啊!
至少我不是很会 呃呃 想了2h才想出来
首先我们先判原串是否合法这里我们可以用前缀和都>=0 就可以了 其实这种合法括号的题 前缀和都很合适
然后我们可以思考一个性质 我手动模拟了几组 猜了一个最多交换次序不会超过2(最后发现是对的
那么如何证明呢???
因为我们要尽量把左括号放前面 我们前缀和最大时我们设当前最大值为si
我们交换1到i i+1到2n(这只是一个构造的
我们值转换后就是 [ai+ai-1+...+a1] + [a2n+a2n-1+...+ai+1]
显然我们j要是小于i 前缀和就是 ai+ai-1+ai-2+...+aj=si-sj-1 因为我们si是max所以恒大于等于0
要是我们j要是大于等于i 前缀和就是 ai+ai-1+...+a1+a2n+a2n-1+...+aj=s2n-sj-1+si s2n==0 si-sj-1显然大于0
那么我们再来讨论 何时输出1就可以了
首先我们考虑要是si出现了<0的点 肯定要包括进去
那么我们维护了一个区间 让后这个区间显然不是最优的
最优的情况是 我们前面囤积了很多左括号 后面能拿到很多的左括号
而这刚好可以用这个前缀和表示 因为我们已经把不合法的区间维护好了 所以我们后面扩展时不用考虑合法性 就算翻转过后还是合法的 那我们贪心的去求l-1的max 以及 r的max 即可
其实这个si的max 也是 根据第二个证明的启发吧 也算情有可原
因为就我们单单翻转维护好的不合法区间 显然不是最优的 我们可以做一些铺垫来get最优解
#include <bits/stdc++.h> using namespace std; const int N = 1e4+10; const int M = 1<<10; const int mod = 1e9+7; #define int long long #define endl '\n' #define Endl '\n' #define YES cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; #define _ 0 #define inf 0x3f3f3f3f3f3f3f3f #define fast ios::sync_with_stdio(false);cin.tie(nullptr); void solve() { int n;cin>>n; vector<int>a(n*2+1); vector<int>s(n*2+1); int flag=0,l,r; for(int i=1;i<=n<<1;i++){ char c;cin>>c; if(c=='(')a[i]=1; else a[i]=-1; s[i]=s[i-1]+a[i]; if(s[i]<0&&flag==0)l=i; if(s[i]<0)r=i,flag=1; } if(!flag){ cout<<0<<endl; return; }else{ int mx=0,pos; for(int i=1;i<=n<<1;i++){ if(mx<s[i]){ mx=s[i]; pos=i; } } int r1=r; for(int i=r1;i<=n<<1;i++){ if(s[i]>s[r])r=i; } int l1=l; for(int i=1;i<=l1;i++){ if(s[i-1]>s[l-1])l=i; } vector<int>b=a; for(int i=l,j=r;i<=r;i++,j--)a[i]=b[j]; for(int i=0;i<=n<<1;i++)s[i]=0; for(int i=1;i<=n<<1;i++){ s[i]=s[i-1]+a[i]; if(s[i]<0){ cout<<2<<endl; cout<<1<<' '<<pos<<endl; cout<<pos+1<<' '<<n*2<<endl; return; } } cout<<1<<endl; cout<<l<<' '<<r<<endl; } } signed main(){ fast int T;cin>>T; while(T--){ solve(); } return ~~(0^_^0); }