美文网首页
爱奇艺-笔试刷题2018-07-12

爱奇艺-笔试刷题2018-07-12

作者: Dodo159753 | 来源:发表于2018-07-12 07:38 被阅读0次

    题目描述:

    /**
    时间限制:1秒
    空间限制:32768K
    牛牛养了n只奶牛,牛牛想给每只奶牛编号,这样就可以轻而易举地分辨它们了。
    每个奶牛对于数字都有自己的喜好,
    第i只奶牛想要一个1和x[i]之间的整数(其中包含1和x[i])。
    牛牛需要满足所有奶牛的喜好,
    请帮助牛牛计算牛牛有多少种给奶牛编号的方法,输出符合要求的编号方法总数。
    输入描述:
    输入包括两行,
    第一行一个整数n(1 ≤ n ≤ 50),表示奶牛的数量
    第二行为n个整数x[i](1 ≤ x[i] ≤ 1000)
    输出描述:
    输出一个整数,表示牛牛在满足所有奶牛的喜好上编号的方法数。
    因为答案可能很大,输出方法数对1,000,000,007的模。
    输入例子1:
    4
    4 4 4 4
    输出例子1:
    24
    */ 
    
    

    思路如下:

    对x[i]升序排序,然后按着升序顺序遍历
    x[i]<=x[i+1]说明x[i]选择就会影响x[i+1]
    对于x[i]来说其可以选择的位置只有 x[i]-i个位置

    然后由乘法原理累乘即可得到全部组合

    代码如下:

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
     
    #define MAX_N 55
    #define MOD 1000000007
     
    using namespace std;
     
    int x[MAX_N];
     
    int main()
    {
        int N;
        scanf("%d", &N);
        for(int i=0; i<N; i++)
            scanf("%d", x+i);
        sort(x, x+N);
        long long res=1;
        for(int i=0; i<N; i++){
            if(x[i]<=i){
                res=0;
                break;
            }
            res*=(long long)(x[i]-i);
            res%=MOD;
        }
        printf("%lld", res);
        return 0;
    }
     
    
    

    相关文章

      网友评论

          本文标题:爱奇艺-笔试刷题2018-07-12

          本文链接:https://www.haomeiwen.com/subject/cwclpftx.html