CF1784B Letter Exchange 题解

FFTotoro · 2023-02-06 22:10:44 · 题解

前言

赛时写了 45\operatorname{min}，差点把人写吐。

解法

本题需要使用贪心算法与双指针处理技巧。

先将所有的字符串按照 \texttt{w} 个数为第一关键字，\texttt{i} 个数为第二关键字排序，然后令 l=1，r=n，两个指针从两边往中间靠拢，不断将 l 处有多余 \texttt{w} 的字符串的 \texttt{w} 从 r 指向的字符串中“换”一个它有多的字母，如果不能换了就跳出。

然后再按照同样的方式排序一次，将还有多余 \texttt{w} 的全部换完。

最后按照 \texttt{i} 个数为关键字排序，把多余的 \texttt{i} 换成 \texttt{n} 即可。

实现可以借助 STL 中的多元组 std::tuple。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int,int> tpi;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<tpi> a(n);
    vector<tuple<int,char,int,char> > v;
    for(int i=0;i<n;i++){
      string s; cin>>s;
      a[i]=make_tuple(i,count(s.begin(),s.end(),'w'),count(s.begin(),s.end(),'i'),count(s.begin(),s.end(),'n'));
    } // 统计字符个数
    sort(a.begin(),a.end(),[](tpi x,tpi y){return get<1>(x)==get<1>(y)?get<2>(x)>get<2>(y):get<1>(x)>get<1>(y);});
    int l=0,r=n-1;
    while(l<r){
      if(get<1>(a[l])<2)break;
      if(get<1>(a[l])==3){
        char c; get<1>(a[l])--,get<1>(a[r])++;
        if(get<2>(a[r])>1)get<2>(a[r])--,get<2>(a[l])++,c='i';
        else get<3>(a[r])--,get<3>(a[l])++,c='n';
        v.emplace_back(get<0>(a[l]),'w',get<0>(a[r]),c);
      } // 有 3 个 w
      else if(get<1>(a[l])==2){
        char c; get<1>(a[l])--,get<1>(a[r])++;
        if(get<2>(a[r])>1)get<2>(a[r])--,get<2>(a[l])++,c='i';
        else get<3>(a[r])--,get<3>(a[l])++,c='n';
        v.emplace_back(get<0>(a[l]),'w',get<0>(a[r]),c);
      } // 有 2 个 w
      else break; // 没必要继续处理
      l++,r--;
    } // 第一轮
    sort(a.begin(),a.end(),[](tpi x,tpi y){return get<1>(x)==get<1>(y)?get<2>(x)>get<2>(y):get<1>(x)>get<1>(y);});
    l=0,r=n-1;
    while(l<r){
      if(get<1>(a[l])<2)break;
      if(get<1>(a[l])==2){
        char c; get<1>(a[l])--,get<1>(a[r])++;
        if(get<2>(a[r])>1)get<2>(a[r])--,get<2>(a[l])++,c='i';
        else get<3>(a[r])--,get<3>(a[l])++,c='n';
        v.emplace_back(get<0>(a[l]),'w',get<0>(a[r]),c);
      }
      l++,r--;
    } // 第二轮
    sort(a.begin(),a.end(),[](tpi x,tpi y){return get<2>(x)==get<2>(y)?get<3>(x)>get<3>(y):get<2>(x)>get<2>(y);});
    l=0,r=n-1;
    while(l<r){
      if(get<2>(a[l])<2)break;
      v.emplace_back(get<0>(a[l]),'i',get<0>(a[r]),'n');
      l++,r--;
    } // 第三轮
    cout<<v.size()<<'\n';
    for(auto [a,b,c,d]:v)
      cout<<a+1<<' '<<b<<' '<<c+1<<' '<<d<<'\n';
  }
  return 0;
}