CF31C题解

jxbe6666 · 2022-02-07 20:17:28 · 题解

题意：要使 n 组的课程没有两个时间段相交。

思路：

对于每种课都判断一下是否需要取消，用 \text{sum} 数组来存。判断完之后从前枚举一边，将答案放到一个数组中。因为不知道有多少种，用 \text{vector} 来存。

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

代码：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x = 0, y = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        y = (c == '-') ? -1 : 1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return x * y;
}
int l[5005], r[5005], s = 0, sum[5005];
int n;
vector<int> ans; // vector
int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        l[i] = read(), r[i] = read(), sum[i] = 0;
    }
    for (int i = 1; i <= n; i++) //要双重循环
        for (int j = 1; j < i; j++)
        {
            if (l[i] < r[j] && l[j] < r[i]) //判断是否要取消
            {
                sum[i]++;
                sum[j]++;
                s++;
            }
        }
    for (int i = 1; i <= n; i++)
        if (sum[i] == s)
            ans.push_back(i);
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}