Educational Codeforces Round 104-C Minimum Ties
題目
思路
首先我們要確定在不重復比賽的情況下一共會有
n
?
(
n
?
1
)
/
2
n*(n-1)/2
n?(n?1)/2場比賽，這樣的話每場比賽可以貢獻一勝一負或者兩負，
所以我們遍歷最多有多少勝場這樣可以保證平局最少
同時很重要的一點總分一定要可以平均分配給每個隊伍，
在滿足以上條件下你可以找到總的勝利場數將它合理的分配給每個球隊即可，而對于平局則當知道每個隊勝場之后也可知道，
代碼
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int a[105];//存盤每個球隊勝場
int b[105];//儲存平局數
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int sum = n * (n - 1);
int temp = n * (n - 1) / 2;
int l1;
for (; temp >= 0; temp--) {
int loop = temp * 3 + (sum - temp * 2) * 1;//總分
if (loop % n == 0) {
l1 = loop / n;//l1是每個球隊最后的分數
break;
}
}
for (int i = 1; i <= n; i++) {
if (temp == 0) {
break;
}
for (int j = 1; i <= n; j++) {
if ((l1 - 3 * j) >= 0) {
a[i] = j;//將勝場分配
} else {
break;
}
}
}
for (int i = 1; i <= n; i++) {
b[i] = l1 - a[i] * 3;//平局
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] != 0) {
a[i]--;//現將勝利的輸出之后是平局最后是負場
printf("1 ");
continue;
} else if (b[i] != 0) {
b[i]--;//一個平局兩個隊都要更新
b[j]--;
printf("0 ");
continue;
} else {
printf("-1 ");
a[j]--;//這個隊負勢必另一個隊勝
}
}
}
printf("\n");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260328.html
標籤：其他