首页 > 代码库 > 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(推导)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。