[codeforces Gym - 100187K] + 구성+욕심

K. Perpetuum Mobile time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output The world famous scientist Innokentiy almost finished the creation of perpetuum mobile. Its main part is the energy generator which allows the other mobile’s parts work. The generator consists of two long parallel plates with n lasers on one of them and n receivers on another. The generator is considered to be working if each laser emits the beam to some receiver such that exactly one beam is emitted to each receiver.
It is obvious that some beams emitted by distinct lasers can intersect. If two beams intersect each other, one joule of energy is released per second because of the interaction of the beams. So the more beams intersect, the more energy is released. Innokentiy noticed that if the energy generator releases exactly k joules per second, the perpetuum mobile will work up to 10 times longer. The scientist can direct any laser at any receiver, but he hasn’t thought of such a construction that will give exactly the required amount of energy yet. You should help the scientist to tune up the generator.
Input The only line contains two integers n and k (1 ≤ n ≤ 200000, ) separated by space — the number of lasers in the energy generator and the power of the generator Innokentiy wants to reach.
Output Output n integers separated by spaces. i-th number should be equal to the number of receiver which the i-th laser should be directed at. Both lasers and receivers are numbered from 1 to n. It is guaranteed that the solution exists. If there are several solutions, you can output any of them.
Examples input 4 5 output 4 2 3 1 input 5 7 output 4 2 5 3 1 input 6 0 output 1 2 3 4 5 6
역서수의 개수는 k~처음에 오름차순으로 배열되고 매번 현재의 첫 번째 L과 마지막 R을 교환하며 매번 공헌은 원소의 개수num+=n*2-3, L++, R-, n-=2이다.이전에 L, R을 교환했을 때 공헌도가 K보다 크면 실행: 나머지 첫 번째 요소인 L을 가능한 한 뒤로 옮겨서 LAC 코드:

#include
#include
using namespace std;
const int K = 2e5 + 10;
typedef long long LL;
int a[K];
int main()
{
    LL n,k;
    scanf("%lld %lld",&n,&k);
    for(int i = 1; i <= n; i++) a[i] = i;
    LL num = 0,pr = n,pl = 1,kl = n;
    while(num < k){
        if(num + kl * 2 - 3 <= k) swap(a[pl++],a[pr--]),num += kl * 2 - 3,kl -= 2;
        else{
            int i,j;
            for(i = pl + 1,j = 1; i < pr; i++,j++)
                if(num + j == k)
                    break;
            num += j;
            int p = a[pl];
            for(j = pl + 1; j <= i; j++)
                a[j - 1] = a[j];
            a[i] = p;
            pl++,pr--;
          }
    }
    for(int i = 1; i <= n; i++)
        printf("%d ",a[i]);
    return 0;
}