首页 > 代码库 > UVA1315 - Crazy tea party(推导)

UVA1315 - Crazy tea party(推导)

题目链接


题意:n个人坐成环形,相邻的两个可以交换位置,求最少交换次数使得序列相反。

思路:类似与冒泡排序,可以将环形序列拆成两个序列,分别进行冒泡。当n为奇数时,分为n/2与n/2 + 1,所以ans = (n / 2) * (n / 2 - 1) / 2 + (n / 2) * (n / 2 + 1) / 2,当n为偶数时,分为两个n/2, 所以ans = (n / 2) * (n / 2 - 1)。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);    
        if (n == 1 || n == 2)  
            printf("0\n");
        else {
            int ans;
            if (n % 2 == 0) {
                ans = (n / 2) * (n / 2 - 1);
                printf("%d\n", ans);
            }
            else {
                ans = (n / 2) * (n / 2 - 1) / 2 + (n / 2) * (n / 2 + 1) / 2;
                printf("%d\n", ans); 
            } 
        } 
    }
    return 0;
}


UVA1315 - Crazy tea party(推导)