Wannafly挑战赛15

最小化价格

题目描述

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

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

输入描述:

1
2
3

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

输出描述:

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

示例1

输入

输出

备注:

所有数据小于1e5

题解

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

代码

#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
2

3
3 4 5

输出

备注:

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)。

代码

#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

3
2
4

说明

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

备注:

1 2	q≤500000 n和x≤1e18

代码

#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;
}