练手速用的，难度在1200~1600之间。
C. Game with Multiset
链接：https://codeforces.com/problemset/problem/1913/C
分数：1300
题意：
给你一个空序列，有以下两种操作：
1、加x , 将 2^x 加入到序列中。
2、给定w ,问是否能从序列中取出若干个元素(不能重复取同一元素)凑出 w
题解：贪心
用cnt数组保存2的i次方位，将v进行拆位，最高位能减就减，依次到低位。
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
| int v[35],f[35];
void init() {
f[0] = 1;
for(int i=1;i<=29;i++) f[i] = f[i - 1] * 2;
}
void JiuCherish(){
int n;
std::cin >> n;
while(n--) {
int op;
std::cin >> op;
if(op == 1) {
int x;
std::cin >> x;
v[x]++;
} else {
int x;
std::cin >> x;
for(int i=29;i>=0;i--) {
x -= f[i] * std::min(x / f[i],v[i]);
}
if(x) std::cout << "NO" << endl;
else std::cout << "YES" << endl;
}
}
}
|
C. Heavy Intervals
链接：https://codeforces.com/problemset/problem/1909/C
分数：1400
题意：
给你一个 l,r,c 数组 ,并重排这三个数组，求重排后权重之和最小可能为多少，权重计算：C_i * (r_i * l_i) 保证每个 i th都满足 r > l。
题解：贪心
用multset维护 l，然后找到小于r[i] 最大的一个，然后通过lower_bound找出大于等于 r[i] 中最小的，用 r[i] - l[i] 的结果丢进 a[i] 里即可。
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
| i64 l[MAXN],r[MAXN],c[MAXN];
i64 a[MAXN];
void JiuCherish(){
int n;
std::cin >> n;
std::multiset<int> q;
for(int i=1;i<=n;i++) {
std::cin >> l[i];
q.insert(l[i]);
}
for(int i=1;i<=n;i++) std::cin >> r[i];
for(int i=1;i<=n;i++) std::cin >> c[i];
std::sort(r + 1,r + n + 1);
std::sort(c + 1,c + n + 1);
for(int i=1;i<=n;i++) {
auto x = q.lower_bound(r[i]);
x--;
a[i] = r[i] - (*x);
q.erase(x);
}
std::sort(a + 1,a + 1 + n);
std::sort(c + 1,c + n + 1);
std::reverse(c + 1,c + n + 1);
i64 ans = 0;
for(int i=1;i<=n;i++) ans += a[i] * c[i];
std::cout << ans << endl;
}
|