#

a

给定一个数n，1 2 3 4 … n 每个数不在原位，求最小移动次数，对应的序列
分别讨论n为偶数和奇数的情况

#include <bits/stdc++.h>
using namespace std;
int main()
{ 
    int t, n;
    scanf("%d", &t);
    while(t--){ 
        scanf("%d", &n);
        if(n%2==0) for (int i = 2; i <= n; i+=2)
        { 
            printf("%d %d ",i,i-1);
        }else{ 
            int a[105];
            for(int i =1; i <= n; i++) a[i] = i;
            for (int i = 1; i <= n; i+=2){ 
                if(i+2==n) { 
                    printf("%d %d %d",a[i+2],a[i],a[i+1]);break;
                }
                else printf("%d %d ",a[i+1],a[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

b

给定一个长为n的序列，满足
i < j i < j i n j > n j>n 和 i > = j i >= j i>=j位置剪枝掉
注意两个数的大小是 1 0 5 10^5 105乘的时候要扩展一下范围

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{ 
   int t; scanf("%d",&t);
   while(t--)
   { 
        int n; scanf("%d",&n);
        int a[n+10];
        for(int i =1; i <= n; i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i =1; i <= n; i++) 
        { 
            int tmp = 1;
            while(1){ 
                int x = tmp * a[i];
                int j = x - i;
                if(j > n) break;
                if(j > i && (ll)a[i]*a[j] == (ll)(i+j)) ans++;
                tmp++;
            }
        }
        printf("%d\n",ans);
   }
}

c

权值最小，建立一个正向边，建立尽可能多的反向边。
正向边最小的长度： a r r [ n − 1 ] arr[n-1] arr[n−1]
反向边：在这里插入图片描述

orz的代码，截过来了：

#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<ll> vl;
void solve()
{ 
    ll n; scanf("%lld",&n);
    vl arr(n);
    for(int i = 0;i<n;i++) cin >> arr[i];
    sort(all(arr));
    ll ans = arr[n-1];
    vl neg(n);
    neg[0] = 0;
    for(int i = 1;i<n;i++){ 
        neg[i] = neg[i-1] + i*(arr[i] - arr[i-1]);
        ans -= neg[i];
    }
    printf("%lld\n", ans);
}
int main(){ 
    int t = 1;
    cin >> t;
    while(t--)
        solve();
      return 0;
}