6 条题解

  • 0
    @ 2022-2-11 17:40:42
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int MAXN = 1e5 + 10;
    
    int n,lens = 1,lenm = 1,lena = 1;
    int sum[MAXN] = {0,1}, Max[10010] = {0, 1}, ans[MAXN];
    struct node{
    	long long l, r, all;
    	void read(){
    		cin >> l >> r;
    		all = l * r;
    	}
    }coin[MAXN];
    bool operator< (node a,node b){
    	return a.all < b.all;
    }
    void mul(long long x){
    	int tmp = 0;
    	for(int i = 1;i <= lens; i++){
    		sum[i] *= x;
    	}
    	for(int i = 1;i <= lens; i++){
    		tmp += sum[i];
    		sum[i] = tmp % 10;
    		tmp /= 10;
    	}
    	while(tmp != 0){
    		lens++;
    		sum[lens] = tmp % 10;
    		tmp /= 10;
    	}
    }
    void work(long long x){
    	memset(ans, 0, sizeof(ans));
    	lena = lens;
    	int tmp = 0;
    	for(int i = lena; i >= 1; i--){
    		tmp *= 10;
    		tmp += sum[i];
    		if(tmp >= x){
    			ans[i] = tmp / x;
    			tmp %= x;
    		}
    	}
    	while(ans[lena] == 0){
    		if(lena == 1){
    			break;
    		}
    		lena--;
    	}
    }
    void chose(){
    	if(lena > lenm) {
    		for(int i = 1;i <= lena; i++){
    			Max[i] = ans[i];
    		}
    		lenm = lena;
    	}
    	else if(lena == lenm){
    		for(int i = lena;i >= 1; i--){
    			if(Max[i] < ans[i]){
    				for(int j = 1;j <= lena; j++){
    					Max[j] = ans[j];
    				}
    				lenm = lena;
    				break;
    			}
    		}
    	}
    }
    int main(){
    	cin >> n;
    	cin >> coin[0].l >> coin[0].r;
    	for(int i = 1;i <= n; i++){
    		coin[i].read();
    	}
    	sort(coin + 1, coin + n + 1);
    	for(int i = 1;i <= n; i++){
    		mul(coin[i - 1].l);
    		work(coin[i].r);
    		chose();
    	}
    	for(int i = lenm; i >= 1; i--){
    		cout << Max[i];
    	}
    	return 0;
    }
    

    信息

    ID
    25
    时间
    1000ms
    内存
    128MiB
    难度
    1
    标签
    递交数
    140
    已通过
    107
    上传者