ICPC-CCPC/308-6.cpp at main · SkyEyeController/ICPC-CCPC · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p pair<int, int>
multiset<p> discount;
multiset<p,greater<p>> workplace;
multiset<int> price; // 全局应用的是大于为小于，所以lower_bound也有变化，变为查找第一个比目标元素小的
int a[200001], b[200001], c[200001];
int n, m;
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        price.insert(a[i]);
    }
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> c[i];
        discount.insert(p(b[i], c[i]));
    }
    int ans = 0;
    while (!price.empty())
    {
        if (discount.empty())
        {
            ans += (*price.begin());
            price.erase(price.begin());
            // 回忆，multiset的erase函数如果传入的是一个数字，将会删除集合中所有的这个数字；如果传入的是一个迭代器，只删除这一个。
            continue;
        }
        int pnow = *(price.begin());
        price.erase(price.begin());
        auto it=discount.upper_bound({pnow,pnow});
        if(it==discount.begin())
        {
            ans+=pnow;
            continue;
        }
        else
        {
            workplace.clear();
            for(auto i=discount.begin();i!=it;i++)
            {
                workplace.insert({(*i).second,(*i).first});
            }
            discount.erase(discount.begin(),it);
            auto i=workplace.begin();
            ans+=pnow-(*i).first;
            workplace.erase(i);
            for(auto i=workplace.begin();i!=workplace.end();i++)
            {
                discount.insert({(*i).second,(*i).first});
            }
        }
    }
    cout << ans << endl;
    system("pause");
    return 0;
}*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p pair<int, int>
multiset<p, greater<p>> discount;
multiset<int> price; // 全局应用的是大于为小于，所以lower_bound也有变化，变为查找第一个比目标元素小的
int a[200001], b[200001], c[200001];
int n, m;
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        price.insert(a[i]);
    }
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> c[i];
        discount.insert(p(c[i], b[i]));
    }
    int ans = 0;
    while (!price.empty())
    {
        if (discount.empty())
        {
            ans += (*price.begin());
            price.erase(price.begin());
            // 回忆，multiset的erase函数如果传入的是一个数字，将会删除集合中所有的这个数字；如果传入的是一个迭代器，只删除这一个。
            continue;
        }
        auto disit = discount.begin();
        auto it = price.lower_bound((*disit).second);
        if (it != price.end())
        {
            ans += (*it) - (*disit).first;
            price.erase(it);
        }
        discount.erase(disit);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}