codeforces 610C

题意：有n个题，难题要花费b分钟，简单的花费a分钟，（a<b）每个题有一个规定的期限，必须在这个时间之前完成它。求最多能够完成几道题。

思路：先按期限从小到大排序，数出总共的简单题数量和总共的难题的数量，循环n次，判断一下前面所花费的总时间是不是小于当前这个题的期限。如果小于的话，就优先考虑简单题，判断能不能把简单题全部做完。如果能的话，当前可能完成的最多的题数就等于简单题的总数，加上能完成的最多的难题；  如果不能的话，当前可能完成的最多的题数就是前面的难题数加上最多可能完成的简单题的数量。

也就是贪心的优先选择简单题做，因为它的时间更短，然后再考虑难题。

#pragma warning(disable:4996)
#include<climits>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
struct node
{
	ll t, x;
};
node point[200005];//保存ti和题的类型
bool cmp(node x, node y)
{
	return x.t < y.t;
}//按ti从小到大排序
int main()
{
	ll i,j,T, n, t, a, b, tot1, tot0,ans;
	scanf("%lld", &T);
	while (T--)
	{
		scanf("%lld%lld%lld%lld", &n, &t, &a, &b);
		tot0 = 0; tot1 = 0; ans = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%lld", &point[i].x);
			if (point[i].x == 0)tot0++;
			else tot1++;
		}//简单的题的数量和难得题得数量
		for (i = 0; i < n; i++)
		{
			scanf("%lld", &point[i].t);
		}
		sort(point, point + n, cmp);
		ll num1=0, num0=0;
		for (i = 0; i < n; i++)
		{
			if ((num0*a + num1 * b) < point[i].t)//当前简单题和难题的总耗时
			{
				if ((tot0*a + num1 * b) >= point[i].t)//全部的简单题和前面的难题
				{
					ans = max(ans, (num1+(point[i].t - 1 - num1 * b) / a));
					//当前的难题数量加上最多的简单题的数量
				}
				else
				{
					ans = max(ans, (tot0 + (point[i].t - 1 - tot0 * a) / b));
					//全部的简单题和最多的难题
				}
			}
			if (point[i].x == 0)num0++;
			else num1++;
		}
		if ((tot0*a + tot1 * b) <=t)//全部都可以取
			ans = n;
		printf("%lldn", ans);
	}
	return 0;
}

最后

以上就是优雅自行车为你收集整理的codeforces 610C的全部内容，希望文章能够帮你解决codeforces 610C所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。