暴力70pts求调
  • 板块P1537 弹珠
  • 楼主FateReset_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/12 16:49
  • 上次更新2023/11/3 10:17:08
查看原帖
暴力70pts求调
365371
FateReset_楼主2023/7/12 16:49
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<windows.h>
/*
  玛莎和比尔拥有一批弹珠。他们想把这批弹珠平分,这样两人都能得到相同份额的弹珠。如果所
  有的弹珠都具有相同的价值,这就很容易了,因为这样他们就可以将收藏品分成两半。但不幸的
  是,有些弹珠比其他弹珠更大或更漂亮。因此,玛莎和比尔首先给每颗弹珠分配一个值,一个介
  于1到6之间的自然数。现在他们想把这些弹珠分开,这样每个弹珠的总价值就相同了。不幸的
  是,他们意识到这样分弹珠可能是不可能的(即使所有弹珠的总价值是偶数)。例如,如果有一
  个价值为1的弹珠,一个价值为3的弹珠和两个价值为4的弹珠,那么就不能将它们分成价值相等
  的几组。因此,他们要求您编写一个程序来检查是否可以公平地分割这些弹珠。
  输入
  输入文件中的每一行都描述了一组待分割的弹珠。每行包含六个非负整数 n1 , .. . 因此,上面的
  例子可以用输入行 "1 0 1 2 0 0 "来描述。最大弹珠总数为 20000。
  输入文件的最后一行是 "0 0 0 0 0",不处理这一行。
  输出
  对于每个集合,输出 "Collection #k :",其中 k 是测试用例的编号,然后输出 "Can be divided.
  "或 "Can't be divided."。
  每个测试用例后输出一行空行。
  Sample Input
  
  1 0 1 2 0 0
  1 0 0 0 1 1
  0 0 0 0 0 0
  
  Sample Output
  
  Collection #1:
  Can't be divided.
  Collection #2:
  Can be divided.
  
 */
using namespace std;
/*
  本题沾了数据量的空子,数据量太小,仅仅只有6种弹珠价格,因此可以暴力破解
  申请加强数据量
 */
int freq=1;//freq代表测试用例编号
bool CheckIfDivided(int n1,int n2,int n3,int n4,int n5,int n6){
	int All=n1+n2*2+n3*3+n4*4+n5*5+n6*6;//代表弹珠总值
	if(All%2)
		return false;//若大小本来就无法均分则直接跳过
	int HalfOfAll=All/2;//代表一半的大小,即均分后每人的大小
	int DividingBall=0;//代表当前正在被均分的弹珠总大小
	int LastOneBall=0;//代表最后一次均分的弹珠
	while(DividingBall<HalfOfAll){
		if(n6!=0){
			DividingBall+=6;
			n6-=1;
			LastOneBall=6;
		}
		else if(n5!=0){
			DividingBall+=5;
			n5-=1;
			LastOneBall=5;
		}		
		else if(n4!=0){
			DividingBall+=4;
			n4-=1;
			LastOneBall=4;
		}
		else if(n3!=0){
			DividingBall+=3;
			n3-=1;
			LastOneBall=3;
		}
		else if(n2!=0){
			DividingBall+=2;
			n2-=1;
			LastOneBall=2;
		}
		else if(n1!=0){
			DividingBall+=1;
			n1-=1;
			LastOneBall=1;
		}
	}
	//若均分后与一半大小相等则可以均分
	if(DividingBall==HalfOfAll)
		return true;
	//否则查看是否需要其他分配珍珠
	else if(DividingBall>HalfOfAll){
		int BiggerNum=HalfOfAll-(DividingBall-LastOneBall);
		if(BiggerNum==1&&n1!=0) return true;
		else if((BiggerNum==2&&n2!=0)||(BiggerNum==2&&n1>=2)) return true;
		else if((BiggerNum==3&&n3!=0)||(BiggerNum==3&&n2>=1&&n1>=1)||(BiggerNum==3&&n1>=3)) return true;
		else if((BiggerNum==4&&n4!=0)||(BiggerNum==4&&n3>=1&&n1>=1)||(BiggerNum==4&&n2>=1&&n1>=2)||(BiggerNum==4&&n1>=4)||(BiggerNum==4&&n2>=2)) return true;
		else if((BiggerNum==5&&n5!=0)||(BiggerNum==5&&n4>=1&&n1>=1)||(BiggerNum==5&&n3>=1&&n2>=1)||(BiggerNum==5&&n3>=1&&n1>=2)||(BiggerNum==5&&n2>=2&&n1>=1)||(BiggerNum==5&&n2>=1&&n1>=2)||(BiggerNum==5&&n1>=5)) return true;
		else if((BiggerNum==6&&n6!=0)||(BiggerNum==6&&n5>=1&&n1>=1)||(BiggerNum==6&&n4>=1&&n2>=1)||(BiggerNum==6&&n4>=1&&n1>=2)||(BiggerNum==6&&n3>=2)||(BiggerNum==6&&n3>=1&&n2>=1&&n1>=1)||(BiggerNum==6&&n3>=1&&n1>=3)||(BiggerNum==6&&n2>=3)||(BiggerNum==6&&n2>=2&&n1>=2)||(BiggerNum==6&&n2>=1&&n1>=4)||(BiggerNum==6&&n1>=6)) return true;
		
	}
	return false;
}
int n1,n2,n3,n4,n5,n6;//分别代表六种价值的弹珠的数量
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	while(cin>>n1>>n2>>n3>>n4>>n5>>n6){
		if(n1==0&&n2==0&&n3==0&&n4==0&&n5==0&&n6==0){
			break;//判断结束
		}else if(CheckIfDivided(n1,n2,n3,n4,n5,n6)){
			cout<<"Collection #"<<freq<<":"<<'\n'<<"Can be divided."<<'\n'<<'\n';
		}else{
			cout<<"Collection #"<<freq<<":"<<'\n'<<"Can't be divided."<<'\n'<<'\n';
		}
		
		freq++;
	}
	
	return 0;
	
}
2023/7/12 16:49
加载中...