CF31C

Buried_Dream · 2021-12-08 20:24:51 · 题解

题意：

给定 n 组课程，给你每组课程的起止时间，

找到所有的方案数使课程不交叉。

思路：

对于每种课都判断一下是否需要取消，用 sum 数组来存。

判断完之后从前枚举一边，将答案放到一个数组中。

因为不知道有多少种，用 vector 来存。

注意下标从 0 开始，放入的时候因该放入 i + 1。

AC code :

#include<bits/stdc++.h>
#define int long long
#define down 0.996
#define T 252
#define lim 1e-15
#define orz cout << "szt lps fjh AK IOI";
using namespace std;

const int maxn = 3e6;
const int MAXN = 3e3;

inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if(ch == '-') {w = -1;}ch = getchar();}
    while (isdigit(ch)) {s = (s << 1) + (s << 3) + (ch ^ 48);ch = getchar();}
    return s * w;
}

inline void print(int x) {
    if (x < 0 ) putchar('-'), x = -x;
    if (x > 9 ) print(x / 10);
    putchar(x % 10 + '0');
}

vector <int> Ans;
int sum[maxn], js = 0;
int a[maxn], b[maxn];

signed main() {
    int n = read();
    for(int i = 0; i < n; i++)  a[i] = read(), b[i] = read();
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < i; j++) 
            if(a[i] < b[j] && a[j] <b [i]) { 
                sum[i]++, sum[j]++, js++;
            }
    for(int i = 0; i < n; i++) if(sum[i] == js) Ans.push_back(i+1);
    cout << Ans.size() << endl;
    for(int i = 0; i < Ans.size(); i++)
        cout << Ans[i] << " ";
    return 0;
}