C++ Groups 分组排班

题意:教师想在5个工作日中选择不同的两天,给学生们上课。给定个n学生们的空闲时间,是偶数。并将学生们分为均等的两组,然后选择其中2天,使得当天上课的所有同学都有空。

来源:https://codeforces.com/contest/1598/problem/B

代码:

#include <iostream>
#define MAXN 15000
#define debug(x) (cout << #x << ":" << x << endl)

typedef long long ll;

using namespace std;

int a[MAXN][10];

int n;

int x, y; // 锁定的两天 

bool judge() {
	int ca = 0, cb = 0, cc = 0; // ca, cb分别统计仅第x, y天有的人数;统计都有空的人数 
	for (int i = 1; i <= n; i++) { 
		int status = a[i][x] + a[i][y];
		if (status == 0) { // 如果两天都没空 
			return false;
		}
		else if (status == 1) { // 如果其中一天有空 
			ca += a[i][x];
			cb += a[i][y];
		} else { // 如果两天都有空 
			cc++;
		}
	}

	if (ca + cc >= n / 2 && (cb + cc >= n / 2))  {
		 debug(ca);
		 debug(cb);
		 debug(cc);
		return true;
	} 
	else return false;
	
	/** 
	 * 错误代码: 
	 * if ((ca + cb + cc) != n) return false; 
	 * if ((ca == cb && (cc % 2 == 0)) || (min(ca, cb) + cc == max(ca, cb))) return true;
	 * 
	 * 错误原因:
	 * 1. 第一行代码是废话,永不执行,因为在 (status == 0) 时已排除。
	 * 2. 第二行代码,“或”的两边其实是等价的(废话),没有考虑到“ca=2, cb=5, cc=5 这种需要同时分给两天”的情况。 
	 */ 
	
}

void solve() {
	
	for (x = 1; x <= 4; x++) {
		for (y = x + 1; y <= 5; y++) {
			if (judge()) {
				cout << "YES" << endl;
				return ;
			}
		}
	}
	cout << "NO" << endl;
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t--) {

		cin >> n;
		
		if (n % 2 == 1) {
			cout << "NO" << endl;
			continue;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 5; j++)
				cin >> a[i][j];
		}

		solve();
		
	}

	return 0;
}


本文标题:《C++ Groups 分组排班》作者:Scar
原文链接:https://aki.cc/post/7.html
特别注明外均为原创,转载请注明。

分享到微信

扫描二维码

可在微信查看或分享至朋友圈。

相关文章

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。