当前位置： 移动技术网 > 移动技术>移动开发>Android > cf1282C 贪心 思维题

cf1282C 贪心 思维题

2020年07月09日  | 移动技术网移动技术  | 我要评论

1282C 1800的题
题意：现有n个题，你要在时间t内做这些题，其中这些题有容易的题表示为0，做完一题的时间为a，难的题表示为1，做完一题的时间为b，且a<b,现在添加一些限制条件，假设你离开的时间为s，那么对于ti<=s的题目将成为你必须要解决的题目，不然你的得分将变为0，现在求你能得到的最大分数是多少
思路：首先对于ti<=s的题目要先做完，然后假设如果你离开的时间为ti-1的话，那么在你完成ti-1之前的问题后，还能最多做出几道题，先做容易题，再做难题，贪心一下。所以这题的思路就出来了，枚举ti-1,即你离开的时间，然后按照上面的来就可以了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, a, n) for(int i = n-1; i >= a; i--)
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define INF 1ll<<60
#define fopen freopen("file.in","r",stdin);freopen("file.out","w",stdout);
#define fclose fclose(stdin);fclose(stdout);
const int maxn = 2e5+10;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct node
{
	int t, degree;
	bool operator < (const node &x)&{
		if(x.t==t){
			return x.degree>degree;
		}else return x.t>t;
	}
};
node c[maxn];
int main(){
	int m;
	m = read();
	while(m--){
		int n=read(), t=read(), a=read(), b=read();
		ll suma=0, sumb=0;
		rep(i,0,n)	{
			c[i].degree=read();
			if(c[i].degree==0) suma++;
			else sumb++;
		}
		rep(i,0,n)	c[i].t=read();
		sort(c, c+n);
		c[n].t=t+1;
		ll cnta=0, cntb=0, ans=0;
		rep(i,0,n+1){
			ll tmp = cnta*a+cntb*b;
			tmp = c[i].t-tmp-1;
			if(tmp>=0){
				ll ia=min(tmp/a, suma-cnta); 
				tmp -= ia*a;
				ll ib=min(tmp/b, sumb-cntb);
				ans = max(ans, cnta+cntb+ia+ib);
			}
			if(c[i].degree==0) cnta++;
			else cntb++;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

本文地址：https://blog.csdn.net/acm123456789ctf/article/details/107200437

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网