[AGC058A] Make it Zigzag 题解

FFTotoro · 2022-10-21 17:29:18 · 题解

前言

赛时 16 分钟过本题，perf 上 \text{\color{Blue}1862}，可惜 Unrated，不然可以上大分。

解法

这道题我用了与官方题解与众不同的做法。

考察每个连续的 p_i,p_{i+1},p_{i+2}(1\le i\le 2n-3,i\equiv1\pmod 2)，容易想到一种贪心：如果 \max\{p_i,p_{i+2}\}>p_{i+1}，那么就将 p_i 于 p_{i+2} 中的较大者与 p_{i+1} 交换，那么这三个数肯定是满足题目条件的，并且对后面的操作不会造成影响。

该操作无后效性的证明：

用我们的方法，后面的操作只会用到 p_{i+2}，而 p_{i+2} 在本次操作中只减不增。同样的 p_i 也只减不增，所以也不会对前面的操作造成影响。

由于操作次数最多为 \frac{2N}{2}=N，所以满足要求。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n<<1),b;
  for(auto &i:a)cin>>i;
  for(int i=0;i<n<<1;i+=2){
    if(i+2>=n<<1){if(a[i+1]<a[i])b.emplace_back(i+1); break;}
    if(a[i+1]>max(a[i],a[i+2]))continue;
    if(a[i]>a[i+2])swap(a[i],a[i+1]),b.emplace_back(i+1);
    else swap(a[i+1],a[i+2]),b.emplace_back(i+2); // 判断与交换
  }
  cout<<b.size()<<endl;
  for(int i:b)cout<<i<<' ';
  cout<<endl;
  return 0;
}