Luobuyu's Blog

0%

1952.金发姑娘和N头牛

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2.6k 阅读时长 ≈ 2 分钟
也是离散化的题目，注意实现方式，可以使用map，也可以手写

1952. 金发姑娘和 N 头牛

题目描述：

你可能听过关于金发姑娘和三只熊的经典故事。

然而，鲜为人知的是，金发姑娘最终成了一个农民。

在她的农场中，她的牛棚里有 $ N $ 头奶牛。

不幸的是，她的奶牛对温度相当敏感。

对于奶牛 $ i $ ，使其感到舒适的温度为 $ A_i \cdots B_i $ 。

如果金发姑娘将牛棚的恒温器的温度 $ T $ 设置为 $ T \le A_i $ ，奶牛就会觉得冷，并会产出 $ X $ 单位的牛奶。

如果她将恒温器的温度 $ T $ 设置在 $ A_i \le T\le B_i $ ，奶牛就会感到舒适，并会产出 $ Y $ 单位的牛奶。

如果她将恒温器的温度 $ T $ 设置为 $ T>B_i $ ，奶牛就会觉得热，并会产出 $ Z $ 单位的牛奶。

正如所期望的那样， $ Y $ 的值始终大于 $ X $ 和 $ Z $ 。

给定 $ X,Y,Z $ 以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。

恒温器温度可设置为任何整数。

输入格式

第一行包含四个整数 $ N,X,Y,Z $ 。

接下来 $ N $ 行，每行包含两个整数 $ A_i $ 和 $ B_i $ 。

输出格式

输出可获得的最大产奶量。

数据范围

输入样例：

1
2
3
4
5
4 7 9 6
5 8
3 4
13 20
7 10

输出样例：

1
31

题解：

注意到，每头牛都是三个区间，温度类似数轴，每次进行三次区间加操作，找到最大值就行了。

由于数比较大，还是需要使用离散化处理。将原数组读下来（所有的 $ A_i, B_i $ ，排序、去重），然后映射到一个新数组，对于映射关系可以使用二分查找。

由于 map 已经保证是有序的了，可以直接使用 map 进行映射。

代码：

map 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int x, y, z;
map<int, int> mp;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x >> y >> z;
    for (int i = 1, a, b; i <= n; i++)
    {
        cin >> a >> b;
        mp[-INF] += x;
        mp[a] += y - x;
        mp[b + 1] += z - y;
        mp[INF] -= z;
    }
    int ans = 0;
    int tmp = 0;
    for (auto &kv : mp)
    {
        tmp += kv.second;
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

手写离散化版本

注意需要搞一个新数组，对原数组的操作转移到新数组上，可以使用二分查找进行转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int x, y, z;
map<int, int> mp;
vector<int> a;
vector<PII> b;
int newa[maxn];
int find(int k)
{
    int l = 0, r = a.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] == k)
            return mid;
        else if (a[mid] > k)
            r = mid - 1;
        else
            l = mid + 1;
    }
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x >> y >> z;
    a.push_back(-INF);
    a.push_back(INF);
    for (int i = 1, l, r; i <= n; i++)
    {
        cin >> l >> r;
        a.push_back(l);
        a.push_back(r + 1);
        b.push_back({l, r});
    }
    sort(a.begin(), a.end());
    // 去重
    a.erase(unique(a.begin(), a.end()), a.end());

    for (auto &item : b)
    {
        int li = find(item.first);
        int ri = find(item.second + 1);
        newa[0] += x;
        newa[li] += y - x;
        newa[ri] += z - y;
        newa[a.size() - 1] -= z;
    }

    int ans = 0;
    int tmp = 0;
    for (int i = 0; i < a.size(); i++)
    {
        tmp += newa[i];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}