题意:教师想在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; }
http://www.jinpaibeer.cn/post/11733.html