CodeForces-629B-Far Relative’s Problem(贪心)

发布于 2019-07-19  1.53k 次阅读


问题传送门:

题意:

小白想邀请他的好友参加一次聚会,具体哪一天未确定,但是已知第i个朋友的性别,
且该朋友在第a​i​到b​i这几天有时间参加(包含a​i和b​i)。
小白希望参加的朋友的男女数量刚好相等,且能参加的人数越多越好。 
Input Data
第一行:一个整数n,表示朋友的数量。
接下来n行,分别是一个字符‘F’或者‘M’,分别表示女和男;两个整数,分别表示a​i和b​i。
Output Data
输出共一个数,表示在男女数量相等的情况下,最多可以有多少个朋友参加派对。

分析:

这一题和

hdu 4883

 很一样。就是要考虑一下性别。

分别统计每一天能到的所有男生人数 和 女生人数。

然后遍历一遍日期,某天男女数量不等时 取最小的那个。

最后取最大,最后乘2。。。

代码:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

typedef long long LL;

const int MAXN = 5e3+10;

struct Node
{
    int numb, numg;
}a[400];

int main()
{
    int n, L, R;
    int minL = 400;
    int maxR = 0;
    char sex;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> sex >> L >> R;
        minL = min(minL, L);
        maxR = max(maxR, R);
        for (int j = L; j <= R; j++)
        {
            if (sex == 'F')
                a[j].numg ++;
            else
                a[j].numb ++;
        }
    }
    int ans = 0;

    for (int i = minL; i <= maxR; i++)
    {
        ans = max(ans, min(a[i].numb, a[i].numg));
    }

    cout << 2*ans << endl;
        
    return 0;
}

Simple And Clear