SHOI2001_Panda的烦恼

发表于 更新于 分类于

Problem’s Website

  • SHOI2001_Panda的烦恼

    Solution

  • 这道题我们可以乱搞，用一个数组存计算的数，另一个数组存下一步要乘的数，这个方法是借鉴了洛谷首篇题解的方法。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define Maxn 100010
    using namespace std;
    int sc() {
    	int xx=0,ff=1; char cch;
    	while(cch<'0'|| cch>'9') {
    		if(cch=='-') ff=-ff; cch=gc;
    	}
    	while(cch>='0'&& cch<='9') {
    		xx=xx*10+(cch-48); cch=gc;
    	}
    	return xx*ff;
    }
    int n,k,cnt;
    int a[Maxn],ans[Maxn]={1},b[Maxn];
    namespace Dy {
    	void RPpp() {
    		n=sc(); k=sc();
    		for(int i=1; i<=n; i++)
    			a[i]=sc();
    		while(cnt<k) {
    			int maxx=0x7fffffff,maxi;
    			for(int i=1; i<=n; i++) {
    				if(ans[b[i]]*a[i]<maxx) {
    					maxx=ans[b[i]]*a[i];
    					maxi=i;
    				}
    			}
    			b[maxi]++;
    			if(ans[cnt]!=maxx) ans[++cnt]=maxx;
    		}
    		printf("%d",ans[k]);
    	}
    };
    int main() {
    	Dy::RPpp();
    	return 0;
    }

rp++