250:TheDevice

题意:

你有n个盘子,每个盘子是一个长为m的01串。你还有一台机器,你需要用两个盘子作为它的输入,然后它会在屏幕上输出一个长为m的01串。输出的每一位是对两个盘子的对应位的and,or,xor三种运算中的一种的结果。你需要确定机器在每一位上究竟会做何种运算。你可以用这n个盘子的任意一对来测试这台机器,但是你可能依然不能确定某一位机器究竟是做的何种运算。所以请计算出确定机器的每一位上做的是哪种运算最少还需要几个盘子?

分析:

显然每一位都是独立的,答案就是每一位需要的盘子数量的最大值。我们考虑每一位还需要的盘子数量。区分and和or,需要0和1,0 and 1=0,0 or 1=1;区分and和xor,也需要0和1,0 and 1=0,0 xor 1=1;区分or和xor,需要1和1,1 xor 1=0,1 or 1=1.所以每一位至少需要1个0,2个1.所以这一位还需要的盘子数量就是max(2-这一位是1的盘子数量,0)+max(1-这一位是0的盘子数量)

代码:

int TheDevice::minimumAdditional(vector  plates) {
    int len=plates[0].length(),siz=plates.size(),ret=0;
	for(int i=0;i<len;i++)
	{
		int a[10];
		memset(a,0,sizeof(a));
		for(int j=0;j<siz;j++)
			a[plates[j][i]-'0']++;
		ret=max(ret,max(0,2-a[1])+max(0,1-a[0]));
	}
	return ret;
}

500:TheJediTest

题意:

你有一个小于20层的房子,每一层有一些学生,一直每k个学生需要一个老师,小于k个也要一个老师,每一层的学生可以走到上下范围小于1的楼层,问最少要几个老师。。。

分析:

我们思考,从小到大枚举楼层,设每一层只能想上要人或者取人,我们已知当前层的人数bi,和可以移动的人数ai,如果ai>bi%k>0,那么我们直接把多余的人移动到i+1层,否则我们尽量从i+1层移动人来补全这一层的人数。。。然后递归下一层。。。

为什么这样是对的呢,因为我们发现,i-1层要么在这次操作时已经是k的倍数了,要么从当前层要了人,已知了两层之间重复移动人是没有意义的,所以只用考虑i+1层。。。。

代码:

int ans;
vector vec,flag;
void solve(int now,int k,int siz)
{
	if(now==siz-1)return;
	if(flag[now]>=vec[now]%k)
	{
		flag[now]-=vec[now]%k;
		vec[now+1]+=vec[now]%k;
		vec[now]-=vec[now]%k;
	}
	else
	{
		int ned=k-vec[now]%k;
		if(ned<flag[now+1])
		{
			flag[now+1]-=ned;
			vec[now]+=ned;
			vec[now+1]-=ned;
		}
		else
		{
			vec[now]+=flag[now+1];
			vec[now+1]-=flag[now+1];
			flag[now+1]=0;
		}
	}
	solve(now+1,k,siz);
}
int TheJediTest::minimumSupervisors(vector  students, int K) {
	ans=0;vec=students;
	flag=students;
	solve(0,K,students.size());
	for(int i=0;i<students.size();i++)
	{
		ans+=vec[i]/K;
		if(vec[i]%K!=0)ans++;
	}
	return ans;
}

 

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注