萌新的求助——P1080 国王游戏
查看原帖
萌新的求助——P1080 国王游戏
305891
夜明楼主2020/7/7 22:24

全WA了……

我就想问一下,我的代码在DEV-C++里面#1显示4,正确答案也是4,而洛谷的评测机却评出了1……

数据点1:

3
1 7
6 1
2 3
2 3

数据点2:

4

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m[50005],tail=0,y,ttt=0;
int chu[50005],z[50005],u[50005];
struct dc{
	int cj;
	int le,ri;
}a[10005];
bool cmp(dc x,dc y){
	return x.cj<y.cj;
}
void p(int x){//高精乘法 
	for(int i=0;i<=tail;i++){
		m[i]*=x;
	}
	for(int i=0;i<=tail;i++){
		if(m[i]>9){
			m[i+1]=m[i]/10;
			m[i]%=10;
			if(i==tail)tail++;
		}
	}
}
void q(int x){//高精除法 
	y=0;
	bool g=true;
	memset(chu,0,sizeof(chu));
	for(int i=0;i<=tail;i++)chu[i]=m[i];
	//cout<<"高精乘法:"<<tail<<endl;
	for(int i=tail;i>=0;i--){
		//cout<<chu[i]<<" ";
		if(g&&chu[i]/x==0){chu[i-1]+=chu[i]%x*10;continue;}
		g=false;
		z[y]=chu[i]/x;
		y++;
		chu[i-1]+=chu[i]%x*10;
	}
	//cout<<endl;
	y--;
	for(int i=0;i<=y/2;i++){
		int p=chu[i];
		chu[i]=chu[y-i];
		chu[y-1]=p;
	}
}
void r(){//数组移位 
	memset(u,0,sizeof(u));
	for(int i=0;i<=y;i++){
		u[i]=z[i];
	}
	ttt=y;
}
void s(int x){//高精比较 
	if(ttt<y||x==0){
		r();
		return;
	}else if(ttt>y)return;
	for(int i=0;i<=y;i++){
		if(u[i]<z[i]){
			r();
			return;
		}
	}
}

int main(){
	m[0]=1;
	cin>>n;
	for(int i=0;i<=n;i++){
		cin>>a[i].le>>a[i].ri;
		a[i].cj=a[i].le*a[i].ri;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		p(a[i-1].le);
		q(a[i].ri);
		s(i-1);
		//for(int i=0;i<=tail;i++)cout<<m[i];
		//cout<<endl;
		//for(int i=0;i<=y;i++)cout<<z[i];
		//cout<<endl<<endl;
	}
	for(int i=0;i<=y;i++)cout<<u[i];
	return 0;
}
2020/7/7 22:24
加载中...