2021-04-29 22:02 哈尔滨工业大学 FPGA工程师

关注

求指点第一题

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int n = 0;
 
    while (cin >> n)
    {
        int a1 = 0;
        int b1 = 0;
        vector<int> a;
        vector<int> b;
        long long resnum = 1;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> a1;
            a.push_back(a1);
        }
        for (int i = 0; i < n; ++i)
        {
            cin >> b1;
            b.push_back(b1);
        }
 
        sort(a.rbegin(), a.rend());
        int flag = 0;
        int a_size = (int)a.size();
        int b_size = (int)b.size();
        for(int i=0;i<a_size;++i)
        {
            int sum = 0;
            for (int j=0;j<b_size;++j)
            {
                if (a[i] <= b[j])
                {
                    sum++;
                }
            }
            sum = sum - flag;
            flag++;
            resnum = resnum * sum;
        }
 
        cout << (resnum % 100000007);
    }
}

遍历两个数组，求出所有的方案，一直显示运行超时，麻烦通过的朋友们分享下思路！感谢！#笔试题目#

全部评论

推荐最新楼层

BuggerKing

西安交通大学 Java

java解法

1 回复分享

发布于 2021-04-29 22:13

fox_lyz

吉林大学 C++

我尝试用最小车去匹配人，感觉和最多的人去匹配车是一样的道理啊，但是无法通过全部的测试用例，这是为啥呢？？？？求大佬解答

点赞回复分享

发布于 2021-04-30 10:09

d;jffufni

中央财经大学 Python

求问为什么不对 ··· from bisect import bisect, bisect_left def solve(self, ): self.count = 0 r = sys.stdin.readlines() n = int(r[0][:-1]) a_list = [int(i) for i in sorted(r[1].split(), reverse=True)] b2_list = [int(i) for i in sorted(r[2].split())] b_mark = [0] * n count = 1 for i in range(n): bs = bisect_left(b2_list, a_list[i]) count *= ((n - bs) - i) return count % 100000007 ···

点赞回复分享

发布于 2021-04-29 23:03

没有汽的可乐

门头沟学院 Java

是我的思路有问题吗，求大佬指点 public static void caseNum(int n, long[] num, long[] cap) { Arrays.sort(num); // 人数 Arrays.sort(cap); // 容量 long result = 1; long count = 0; for (int car = 0, i = 0, j = 0; car < n && i< n && j < n;) { while (i < n && cap[j] >= num[i]) { i++; count++; } if (count > (n - car)) { long a = n - car; while (a > 0) { a = a % 100000007; result = (result * (a)) % 100000007; a--; } break; } else { result = result * ((count - car) % 100000007) % 100000007; } j++; car++; } System.out.println(result); }

点赞回复分享

发布于 2021-04-29 22:29

my_offers

北京大学深圳研究生院算法工程师

找到当时的代码了。mark

点赞回复分享

发布于 2021-04-29 22:28

my_offers

北京大学深圳研究生院算法工程师

题目含义：类似田忌赛马。问：大佬赛马，有多少种方式完虐菜鸡？

点赞回复分享

发布于 2021-04-29 22:25

repiv

西安交通大学后端

public static void main(String[] args) { Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n = scanner.nextInt(); int[] count = new int[n], capacity = new int[n]; for (int i = 0; i < n; i++) { count[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { capacity[i] = scanner.nextInt(); } Arrays.sort(count); Arrays.sort(capacity); long res = 1; int right = n - 1; for (int i = n - 1; i >= 0; i--) { while (right >= 0 && capacity[right] >= count[i]) right--; res *= (n - 1 - right) - (n - 1 - i); res %= 100000007; if (res == 0) break; } System.out.println(res); }

点赞回复分享

发布于 2021-04-29 22:24

miamiaoxyz

门头沟学院 Java

加个指针j就好： int j = n,sz = 0,ans = 1; for(int i = n;i>=1;i--) { while(b[j]>=a[i] && j >=1) j--,sz++; ans *= sz%mod;ans%=mod; sz--; }

点赞回复分享

发布于 2021-04-29 22:18

repiv

西安交通大学后端

n^2应该会超时, 我的思路是用二分搜索将时间复杂度降到nlogn

点赞回复分享

发布于 2021-04-29 22:08

牛客377850253号

RWTH Aachen University 算法工程师

def binary_search(arr,target): l,r = 0,len(arr)-1 while l <= r: mid = (l+r)//2 if arr[mid] < target: l = mid + 1 else: r = mid - 1 return l def func(count_list, n, mod): res = 1 for i in range(n): curr = count[i]-i if curr<=0: return 0 res = (res * curr)%mod return res n = int(input().strip()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort(reverse = True) B.sort() count = [] for i in A: idx = binary_search(B, i) count.append(n-idx) mod = 100000007 print(func(count,n,mod))

点赞回复分享

发布于 2021-04-29 22:06

amberamber

西安交通大学算法工程师

同样想法，python写出来也是一直超时😢

点赞回复分享

发布于 2021-04-29 22:05