求调,TLE on #4
  • 板块P3254 圆桌问题
  • 楼主USA_CO
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/7/27 21:22
  • 上次更新2025/7/28 11:00:23
查看原帖
求调,TLE on #4
731671
USA_CO楼主2025/7/27 21:22

code:

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int m,n,r[N],c[N];
int cnt[N];
bool vis[N];
vector<int> ans[N];
struct Table {
    int id, capacity;
    bool operator<(const Table& t) const {
        return capacity > t.capacity;
    }
};
bool dfs(int u, int need) {
    if (need == 0) return true;
    
    vector<Table> tables;
    for (int v : ans[u]) {
        if (cnt[v] < c[v] && !vis[v]) {
            tables.push_back({v, c[v] - cnt[v]});
        }
    }
    for (int v = 1; v <= n; v++) {
        if (find(ans[u].begin(), ans[u].end(), v) == ans[u].end() && 
            cnt[v] < c[v] && !vis[v]) {
            tables.push_back({v, c[v] - cnt[v]});
        }
    }
    sort(tables.begin(), tables.end());
    for (auto& t : tables) {
        int v = t.id;
        vis[v] = true;
        cnt[v]++;
        ans[u].push_back(v);
        
        if (dfs(u, need - 1)) {
            vis[v] = false;
            return true;
        }
        cnt[v]--;
        ans[u].pop_back();
        vis[v] = false;
    }
    
    return false;
}
bool check() {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= m; i++) ans[i].clear();
    for (int i = 1; i <= m; i++) {
        memset(vis, 0, sizeof(vis));
        if (!dfs(i, r[i])) return false;
    }
    return true;
}
int main() {
    cin >> m >> n;
    if (m < 1 || m > 150 || n < 1 || n > 270) {
        cout << 0 << endl;
        return 0;
    }
    int sum1 = 0, sum2 = 0;
    for (int i = 1; i <= m; i++) {
        cin >> r[i];
        if (r[i] < 1 || r[i] > 1000) {
            cout << 0 << endl;
            return 0;
        }
        sum1 += r[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        if (c[i] < 1 || c[i] > 1000) {
            cout << 0 << endl;
            return 0;
        }
        sum2 += c[i];
    }
    if (sum1 > sum2) {
        cout << 0 << endl;
        return 0;
    }
    if (!check()) {
        cout << 0 << endl;
        return 0;
    }
    cout << 1 << endl;
    for (int i = 1; i <= m; i++) {
        sort(ans[i].begin(), ans[i].end());
        for (int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << (j == ans[i].size() - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
2025/7/27 21:22
加载中...