C. Crazy Diamond(思维+构造)-白红宇

C. Crazy Diamond(思维+构造)

阅读量：238 次

发布时间：2019-03-01

本文共 2346 字，大约阅读时间需要 7 分钟。

    
   
    
    
   
    
   
    
   
    思路：数字1和n在排序过程中具有特殊性，常被用作中转站进行值的交换。
    
   
    对于小于等于n/2的数值，处理方式如下：首先将其与n交换位置，再将交换后的数值转移到1的位置。对于大于n/2+1的数值，处理方式与上述相似。
    
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #define debug(a) cout << "#a# " << a << endl; using namespace std;const int maxn = "3e5+1000";typedef long long ll;typedef pair
             
               P;inline LL read() { LL x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }LL a[maxn], pos[maxn];vector
               ans;void op(LL x, LL y) { ans.push_back({x, y}); swap(pos[a[x]], pos[a[y]]); swap(a[x], a[y]); }int main(void) { cin.tie(0); std::ios::sync_with_stdio(false); LL n; cin >> n; for (LL i = 1; i <= n; i++) { cin >> a[i]; pos[a[i]] = i; } for (LL i = 2; i <= n/2; i++) { if (pos[i] <= n/2) { op(pos[i], n); op(n, i); } else { op(pos[i], 1); op(1, n); op(n, i); } } for (LL i = n/2+1; i <= n; i++) { if (pos[i] > n/2) { op(pos[i], n); op(n, i); } else { op(pos[i], 1); op(1, n); op(n, i); } } <#include

经过优化后的版本：

    
   
    
    
   
    
   
    
   
    数字1和n在排序过程中具有特殊性，常被用作中转站进行值的交换。
    
   
    对于小于等于n/2的数值，处理方式如下：首先将其与n交换位置，再将交换后的数值转移到1的位置。对于大于n/2+1的数值，处理方式与上述相似。
    
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #define debug(a) cout << "debug: " << a << endl; using namespace std;const int maxn = 300000 + 1000;typedef long long ll;typedef pair
             
               P;inline ll read() { ll x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }ll a[maxn], pos[maxn];vector
               ans;void op(ll x, ll y) { ans.push_back({x, y}); swap(pos[a[x]], pos[a[y]]); swap(a[x], a[y]); }int main(void) { cin.tie(0); std::ios::sync_with_stdio(false); ll n; cin >> n; for (ll i = 1; i <= n; i++) { cin >> a[i]; pos[a[i]] = i; } for (ll i = 2; i <= n/2; i++) { if (pos[i] <= n/2) { op(pos[i], n); op(n, i); } else { op(pos[i], 1); op(1, n); op(n, i); } } for (ll i = n/2+1; i <= n; i++) { if (pos[i] > n/2) { op(pos[i], n); op(n, i); } else { op(pos[i], 1); op(1, n); op(n, i); } }