935 div2 C. Manhattan Permutations

문제

풀이

조건은 찾았는데 순열을 출력을 못해서 틀렸다....

 

우선 identity permutation 에서 수의 위치를 바꿔 나올 수 있는 최대 차의 합은 역순이다.

그리고 결국 특정 x와 y에 대한 순서를 바꾸게 된다면, abs(x-y) + abs(x-y)이다. 그러므로 두 쌍식 나오게 되므로 홀수가 답이 될 수 없다.

 

순열을 구하기 위해서는 수학적인 규칙을 찾아야된다.

[1, 2, 3, 4, 5, 6 ~~~~ xn] 가 있다고 하자. 

1의 위치를 특정한 xi와 바꾼다고 하면, 그로 인해 발생하는 값은 1 - xi, xi - 1이다. 차의 절댓값의 합으로 나타내야 하므로 결국 (xi - 1) * 2 ( xi > 1 ) 이 된다.

1의 위치와 xi 의 위치를 바꾸는 경우가 위치를 바꾸는 경우의 수 들 중에서 가장 차의 절댓값이 크다.

K가 0이 될때까지, 1과 xi를 바꾸고, 2와 xj를 바꾸고 ~~~ 이렇게 움직이면서 순열을 구하면 된다.

그러므로 1과 끝점을 lo, hi 로 잡고, 이를 투포인터로 움직이면서 어떤 수와 어떤 수가 바뀌는지 구하면 된다. 

 

#include <iostream>

// util
#include <algorithm>
#include <cmath>
#include <stdlib.h>
#include <stdint.h>

// data structure
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <deque>

#define INTMAX 987654321
#define ll long long
#define pii std::pair<int,int>
#define vi std::vector<int>
#define pll std::pair<long long , long long>
#define vl std::vector<long long>
#define for_N(N) for(int i=0; i<N; i++)

using namespace std;
int T;
int main() {
    cin>>T;
    while(T--) {
        ll n, k; cin>>n>>k;
        ll arr[200002]={0};
        for(int i=1; i<=n; i++) arr[i] = i;
        ll max_s = 0;
        for(int i=1; i<=n; i++) {
            max_s += abs(arr[i] - arr[n-i+1]);
        }
        if(k > max_s || k%2 == 1) {
            cout<<"NO\n";
        } 
        else {
            int lo = 1, hi = n;
            while(lo < hi) {
                if(k >= abs(arr[lo] - arr[hi]) * 2) {
                    k -= abs(arr[lo] - arr[hi]) * 2;
                    swap(arr[lo], arr[hi]);
                    lo++;
                    hi--;
                } else {
                    hi --;
                }
            }
            cout<<"YES\n";
            for(int i=1; i<=n; i++) cout<<arr[i]<<" ";
            cout<<'\n';
        }
    }
}