Wannafly挑战赛15

最小化价格

题目描述

要求一种方式,使得每组人都到一个各不相同的地点,最小化选择的价格

每个队伍的人都要在同一个地方每个地方只能有一个队伍

输入描述:

1
2
3
第一行n,m
第二行n个数,表示每组的人数
接下来m行,每行两个数,表示可容纳的最大人数和选择的价格

输出描述:

1
输出最小化选择的价格,无解输出-1

示例1

输入

1
2
3
4
5
6
3 4
2 3 4
1 2
2 3
3 4
4 5

输出

1
12

备注:

1
所有数据小于1e5

题解

首先对地点以价格从小到大排序,如果相同按容量从小到大排序。由于集合每次插入自动排序,而且可以执行删除操作,因此我们可以用集合储存队伍。然后将队伍放入集合中。对排完序的地点进行遍历,每个地点对容量进行判断,直接对集合up_bound-1操作,就是能被该地点容纳的人数最多的队伍。若存在该队伍,将该队伍从集合中删除,意为该队伍匹配到该地点。然后将总价格加上该地点所需的价格。否则不执行操作,意为当前没有队伍能和该地点匹配。最后对集合判断是否为空,若为空,则证明队伍已经匹配完毕,输出总价格即可,否则意为不是所有队伍都能被容纳,输出-1。

代码

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
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int const maxn = 100020;
struct node {
int pri;
int num;
}loc[maxn];
int cmp(node a, node b) {
if (a.pri == b.pri)
return a.num < b.num;
else
return a.pri < b.pri;
}
int main()
{
int n, m, tmp, ans = 0;
cin >> n >> m;
multiset<int>a;
for (int i = 0; i < n; i++) {
cin >> tmp;
a.insert(tmp);
}
for (int i = 0; i < m; i++) {
cin >> loc[i].num >> loc[i].pri;
}
sort(loc, loc + m, cmp);
multiset<int>::iterator it;
for (int i = 0; i < m; i++) {
if (a.empty())
break;
it = a.upper_bound(loc[i].num);
if (it == a.begin())
continue;
it--;
ans += loc[i].pri;
a.erase(it);
}
if (a.empty())
cout << ans << endl;
else
cout << "-1" << endl;
return 0;
}

车辆安排

题目描述

有n个队伍,每个队伍的人数小于等于5,每辆车最多坐5个人,要求一个队伍的人都在一辆车上,求最少的车数

输入描述:

1
2
第一行n
第二行n个数,表示每个队伍的人数

输出描述:

1
输出最少车数

示例1

输入

1
2
3
3 4 5

输出

1
3

备注:

1
2
n≤1e5
每个数小于等于5

题解

设置一个数组,分别储存1,2,3,4,5人队伍的个数。总车数=人数为5的队伍数+(人数为4+1或4的队伍数)+(人数为3+2或3+1+1或3的队伍数)+(人数为2+2+1或2+1+1+1或2的队伍数)+(人数为1*5或1的队伍数),(组合方式按优先级排列)。时间复杂度O(1)。

代码

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
#include<stdio.h>
int main() {
int n, tmp;
scanf("%d", &n);
int a[6] = { 0 }, sum = 0;
while (n--) {
scanf("%d", &tmp);
a[tmp]++;
}
sum += a[5] + a[4] + a[3];
a[1] = a[1] - a[4];
if (a[3] - a[2] > 0)
a[1] -= 2 * (a[3] - a[2]);
a[2] -= a[3];
if (a[2] < 0)
a[2] = 0;
a[1] -= a[2] / 2;
if (a[2] % 2 == 0) {
sum += a[2] / 2;
}
else {
sum += a[2] / 2 + 1;
a[1] -= 3;
}
if (a[1] < 0)
a[1] = 0;
a[1] % 5 == 0 ? sum += a[1] / 5 : sum += a[1] / 5 + 1;
printf("%d\n", sum);
return 0;
}

出队

题目描述

约瑟夫问题(约瑟夫问题),n个人,1 2报数 1出队( 就是体育课的时候1 2报数 1出队,2留下),q次询问,每次求第x个人是第几个出队的

输入描述:

1
2
第一行两个数n,q
接下来q行,每行一个数x,表示询问

输出描述:

1
一行输出一个询问的答案

示例1

输入

1
2
3
4
4 3
2
3
4

输出

1
2
3
3
2
4

说明

1
1 2 3 4围成一圈,第一轮:1 2报数,1出队,2留下,3出队,4留下,第二轮,2出队,4留下

备注:

1
2
q≤500000
n和x≤1e18

代码

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
#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define ll unsigned long long int
map<ll, ll>ma;
vector<ll>v;
int main()
{
int n, q , cnt;
cin >> n >> q;
ma[1] = 1;
cnt = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0)
v.push_back(i);
else {
ma[i] = ++cnt;
}
}
ll it = 0;
if (n % 2)
it++;
while (!v.empty()) {
if (it == v.size())
it = 0;
ma[*(v.begin() + it)] = ++cnt;
v.erase(v.begin() + it);
if (v.empty())
break;
if (it == v.size())
it = 0;
it++;
}
while (q--) {
int x;
cin >> x;
cout << ma[x] << endl;
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!