对于一类构造题来说。都是先找出不能构造的情况，之后再思考构造
在这题当中，如果这个k能够在最小构造次数和最大构造次数之间那就可以构造
现在的问题是如何找到最小和最大。题目说的翻转，我们不如把他看作交换，这样最小的情况其实就是一次交换一次，也就是逆序对的数量
最大的情况就是每次都把所有可以交换的交换掉。首先，我们可以思考，每个相对的在没交换的时候一定还是相对的，也就是肯定要被交换，无论别的队数怎么样，因此每次交换所有可以交换的才是最优的
那么现在考虑如何把次数从最小值慢慢变到最大值。
那肯定想到，比如我们之前可以交换1 3 5这三个位置
我们先交换1 3 ，然后交换5就成功的扩大一次
只要按照这个肯定能够构造出来。
我们考虑从最后一组交换开始，其实也可以从第一次交换开始，但是这样写起来比较复杂。
那只要每次把原来最小的组的最后一位拿出来变成新的就行。如果原来某组已经没有了，那就往前一组。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<map> #include<string> #include<vector> using namespace std; typedef vector<int> VI; const int N=3000010; int n,k; string s; int tot,idx,cnt; vector<int> ans[N]; int main(){ cin>>n>>k; cin>>s; int i,j; while(1){ for(i=0;i<(int)s.size()-1;i++){ if(s[i]==‘R‘&&s[i+1]==‘L‘){ ans[idx].push_back(i); cnt++; } } if(ans[idx].empty()) break; if(idx>=k){ cout<<"-1"<<endl; return 0; } idx++; for(auto x:ans[idx-1]){ swap(s[x],s[x+1]); } } if(k>cnt){ cout<<-1<<endl; return 0; } int m=idx-1; for(i=k-1;i>=0;i--){ if(ans[m].empty()) m--; if(!ans[i].empty()) break; ans[i].push_back(ans[m].back()); ans[m].pop_back(); } for(i=0;i<k;i++){ printf("%d\n",(int)ans[i].size()); for(auto x:ans[i]){ printf("%d ",x+1); } printf("\n"); } return 0; }
CF1333D Challenges in school №41（思维）
原文：https://www.cnblogs.com/ctyakwf/p/12718824.html
