首页 > 试题广场 >

孙悟空的徒弟

[编程题]孙悟空的徒弟
  • 热度指数:3694 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

打败魔人布欧以后,孙悟空收了n个徒弟,每个徒弟战斗力各不相同。他教导所有的徒弟和体术,合体后战斗力为原战斗力相乘。任何两个徒弟都可以合体,所以一共有n*(n-1)/2种合体徒弟。有一天,他想考验一下孙悟天战斗力如何,希望在所有n*(n-1)/2种合体徒弟中选择战斗力第k高的,与孙悟天对战。可是孙悟空徒弟太多了,他已然懵逼,于是找到了你,请你帮他找到对的人。


输入描述:
第一行两个int。徒弟数量:n <= 1*10^6;战斗力排名:k <= n*(n-1)/2
第二行空格分隔n个int,表示每个徒弟的战斗力。


输出描述:
战斗力排名k的合体徒弟战斗力。
示例1

输入

5 2
1 3 4 5 9

输出

36
// 二分答案,然后再去找答案。思路和9月1号pdd最后一道类似。
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <set>
#include <queue>
#include <climits>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
using namespace std;
typedef  long long LL;
const int mod = 1e9+7;
using namespace std;
const int inf = 0x7f7f7f7f;
#define _for(i,l,r) for(int i=(l);i<(r);i++)
LL data[1000005];
int main() {
    LL n,k;
    scanf("%lld%lld",&n,&k);
    _for(i,0,n){
        scanf("%lld",&data[i]);
    }
 
    sort(data,data + n);
 
    LL l = data[0] * data[1], r = data[n - 1] * data[n - 2];
    k = n * (n - 1) / 2 - k + 1;
    while(r > l){
        LL mid = (l + r) / 2;
        LL cnt = 0;
        for(LL i = n - 1;i>=0 ;i--){
            LL tmp = mid / data[i];
            if(i) {
                LL index = upper_bound(data, data + i, tmp) - data;
                cnt += index;
            }
        }
        if(cnt >= k){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    LL t = LLONG_MIN;
//    cout << " l : "<< l << endl;
     
    for(LL i = 1;i<n;i++){
        LL tmp = l / data[i];
        LL index = upper_bound(data, data + i, tmp) - data;
        t = max(t,data[i] * data[index - 1]);
    }
    cout << t << endl;
    return 0;
}

发表于 2019-09-10 16:57:17 回复(0)
发表于 2019-09-20 16:11:08 回复(0)
#include <bits/stdc++.h>
using namespace std;
long long check(vector<long long>& att, long long& mid, long long k, long long n)
{
	long long below = 0;
	long long num = 0;
    long long same_p = 0;
	long long min_val = att[n - 1] * att[n - 1] * 2;
	for (long long i = 0; i < n; i++)
	{
		long long pos = upper_bound(att.begin() + i + 1, att.end(), mid / att[i]) - att.begin();
		num += att.size() - pos;
		if (pos == att.size())
			continue;
		long long minu = att[pos] * att[i] - mid;
		if (minu < min_val)
		{
			min_val = minu;
			below = att[pos] * att[i];
            same_p = 0;
		}
        if(minu == min_val)
            same_p++;
	}
	if(k == num || (num > k && num-same_p < k))
    {
        mid = below;
        num = k;
    }
	return num;
}

int main() {
	long long n,k;
	vector<long long> att;
	scanf("%lld %lld", &n, &k);
	long long tmp;
	for (long long i = 0; i < n; i++)
	{
		scanf("%lld", &tmp);
		att.push_back(tmp);
	}
	sort(att.begin(), att.end());
	long long lo = att[0] * att[1];
	long long hi = att[n - 1] * att[n - 2];
	long long ans;
	while (lo <= hi)
	{
		long long mid = (lo + hi) >> 1;
		long long num = check(att, mid, k, n);
		if (num == k)
		{
			ans = mid;
			break;
		}
		if (num > k)
		{
			lo = mid + 1;
		}
		else
			hi = mid - 1;
	}
	printf("%lld\n", ans);
	return 0;
}
AC
发表于 2019-08-20 17:15:58 回复(0)
这个题尽力了,一开始是二分法找mid,然后遍历一遍如果cnt大于k就停下来,通过了65%,后面又在遍历上做了优化,又写了一个二分法找upper_bound,结果还是65% ...... 不知道是python本身就没办法满足这个时间限制还是说有可以继续优化的地方

n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))

nums.sort()

def upper_bound(nums, target):
    low, high = 0, len(nums)-1
    pos = len(nums)
    while low<high:
        mid=(low+high) // 2
        if nums[mid]<=target:
            low = mid+1
        else:#>
            high = mid
            pos = high
    if nums[low]>target:
        pos = low
    return pos

def Smaller(x):
    cnt = 0
    for i in range(len(nums) - 1):
        cnt += len(nums[i+1:]) - upper_bound(nums[i+1:], x // nums[i])
        if cnt >= k: return True
    return False

low, high = nums[0] * nums[1], nums[-1] * nums[-2]
while low < high:
    mid = (low + high) // 2
    if Smaller(mid):
        low = mid + 1
    else:
        high = mid

print(high)


发表于 2019-09-05 22:54:32 回复(2)
这题数据有问题: n=1000000, k=232744003306, 问题是徒弟只有403个, 全部组合只有403*402/2=81003个,怎么找排名那么靠后的组合?
把n,k 改为 403,1~81003 保证通过
1000000 232744003306
5738 5100 2247 6728 4498 5721 3795 6238 4759 4733 5338 8613 4421 1517 4579 7253 3584 1908 2392 3604 7331 3894 2862 6046 7253 1292 5328 5593 7549 4817 5765 2620 7444 6457 5733 8593 2194 9663 3592 510 2240 5482 6997 5035 9843 976 1686 1123 1254 8444 8592 6042 6064 6902 8959 7531 9144 2196 2712 1357 6568 7871 7075 7399 9895 831 4091 226 9979 2780 868 1398 1440 1612 4170 5644 7323 4764 7008 1417 804 5471 2226 6713 7924 8110 6727 5647 4837 4628 9640 8903 2523 8214 7419 1513 8208 701 776 8971 7213 544 5928 5415 1880 8985 3060 3330 2922 7599 7314 6199 6891 9241 8635 4573 2627 4160 6152 6892 8680 8828 655 1706 919 1285 6969 8275 4690 2851 9790 3725 886 7708 6837 543 3320 557 4536 8002 8369 2297 4350 5693 3721 3114 7806 1946 4727 1433 7921 6657 2788 8236 1247 5189 2121 6683 3408 7173 5164 3521 5451 9526 2903 3714 3129 3807 3056 5289 2355 2809 9472 4476 8032 6940 5039 7668 4551 4608 3909 4154 1233 828 5641 4435 6103 5241 1509 331 6286 1360 6639 2950 8065 6216 3744 4719 4166 3208 7472 3693 8503 3801 263 2374 2939 4787 6060 7958 7096 1853 8809 8387 8010 3744 8453 5299 565 1572 5430 9138 2949 4339 4904 5732 1790 240 1281 9251 6490 4824 2040 7288 6401 3295 8854 138 2444 5889 4452 2561 8866 4754 4918 2755 5643 2573 4201 1482 3949 376 4051 4176 7667 7949 4011 5225 8435 8242 1354 9842 3623 2527 8568 2155 6535 5279 8956 8692 1383 2071 6513 2513 8500 2799 3627 7723 5074 1617 661 4027 5229 1059 1638 9895 1881 6703 436 7911 8081 9371 6876 4901 2237 7520 7872 3319 5601 7590 6812 2104 8970 7061 4679 7035 5133 8917 1689 7628 6483 3278 5096 7027 5460 9590 6257 8326 2744 6681 838 3966 4472 2653 6389 1073 3977 1784 5728 3964 9542 261 2724 5377 4468 6075 8149 8221 2958 594 1246 3206 6507 9378 9173 322 9716 5137 5859 492 9614 9532 97 9723 8324 3302 3957 3575 3853 5704 2120 4040 2832 3437 4370 8165 5719 1321 2219 8215 952 4615 8890 1814 5660 925 4889 171 5340 645 2142 9227 1837 1782 7763 7553 5274 71 4271 7908 7994 8321 8105 1163 8372 4507 9785 7295 9010 7616 6921 7480 7739 

发表于 2021-06-10 00:29:38 回复(0)
题目要求第k大的数,则用二分法找出这个数。注意数据过大,需要用long,否则会通不过
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    long n, k;
    scanf("%ld%ld", &n, &k);
    vector<long> A(n);
    for (int i = 0; i < n; ++i)
        scanf("%ld", &A[i]);
    sort(A.begin(), A.end());

    long left = 1, right = A[n-1]*A[n-2];
    while (left<=right)
    {
        long mid = (left+right)/2;
        long count = 0;
        int i = 0, j = n-1;
        while (i < j && count < k)
        {
            while (i < j && A[i]*A[j]<mid) i++;
            count += j-i;
            j--;
        }
        if (count >= k)
            left = mid+1;
        else 
            right = mid-1;
    }
    printf("%ld\n", right);

    return 0;
}

编辑于 2021-01-04 14:28:33 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long k = scan.nextLong();
        
        long[] power = new long[n];
        for(int i=0;i<n;i++){
            power[i] = scan.nextLong();
        }
        Arrays.sort(power);
        long l = 1,r = power[n-1]*power[n-2],mid = 0;
        while(l<r){
            mid = (l+r+1)/2;
            long cnt = 0;
            int left = 0, right = n-1;
            while(left<right && cnt<k){
                while(power[left]*power[right]<mid) left++;
                cnt+=Math.max(right-left,0);
                right--;
            }
            if(cnt>=k) l=mid;
            else r = mid-1;
        }
         System.out.println(l);
    }
}
借鉴大佬们二分思路的Java版本,可以通过。
这道题我的问题就是陷入思维定式,只考虑如何优化剪枝候选的值,没有把他放到[1,power[n-1]*power[n-2]]这一连续区间中考虑
编辑于 2020-07-28 11:13:31 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,k;
    while(cin>>n>>k)
    {
        long arr[n];
        vector<long>tmp;
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                tmp.push_back(arr[i]*arr[j]);
            }
        }
        sort(tmp.begin(),tmp.end());
        cout<<tmp[tmp.size()-k]<<endl;
    }
}


65%怎么说
发表于 2020-06-10 23:38:14 回复(0)
自暴自弃了...最短的65%...
n,k = map(int,input().split())
t = list(map(int,input().split()))
print(sorted([t[i]*t[j] for i in range(n-1) for j in range(i+1,n)])[-k])


发表于 2019-09-15 01:32:11 回复(0)
        long min = 0, max =val[n - 1] * val[n - 2];
        while (min < max) {
            long mid = (min + max + 1) >> 1;
            long cnt = 0;
            int low = 0, high = n - 1;
            while (low < high && cnt < k) {
                while (low < high && val[low] *val[high] < mid) {
                    ++low;
                }
                cnt += high - low > 0 ? high - low : 0;
                --high;
            }
            if (cnt >= k) {
                min = mid;
            } else {
                max = mid - 1;
            }
        }
这个部分有大佬可以讲解一下吗  没太搞明白
发表于 2019-08-28 16:12:30 回复(0)
nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
fight = sorted(list(map(int,input().split())))
res = []
for i in range(0, n-1):
    for j in range(i+1, n):
        num = fight[i] * fight[j]
        res.append(num)
res = sorted(res, reverse = True)
print(res[k - 1])
65%,我觉得不能用暴力求解,应该是找到第K个直接结束循环

发表于 2019-08-19 21:27:19 回复(0)
nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
fight = sorted(list(map(int,input().split())))
res = []
for i in range(0, n):
    for j in range(1, i):
        num = fight[i] * fight[j]
        res.append(num)
res = sorted(res, reverse = True)
print(res[k - 1])

请检查是否存在语法错误或者数组越界非法访问等情况 case通过率为55.00%
发表于 2019-08-18 22:22:42 回复(2)

通过率30% 并不知道自己错在哪儿🤣🤣

nn=list(map(int,input().split()))
n=nn[0]
k=nn[1]
fat=sorted(list(map(int,input().split())))
high=n-1
sum_=0
whilehigh:
    sum_+=high
    ifk-sum_<=0:
        index=sum_-k
        break
    high-=1
print(fat[high]*fat[index])











编辑于 2019-08-14 15:32:38 回复(0)
全正数还可以搞,正负都有如何搞啊QAQ
发表于 2019-08-09 16:21:38 回复(2)
所以这道题有没有AC的解法,而且时间内存都没有超限
发表于 2019-07-15 13:47:43 回复(0)
nn=input().split()
n=nn[0]
k=nn[1]
ls=[]
fat=input().split()
fori inrange(len(fat)-1):
    forj inrange(i+1,len(fat)):
        a=int(fat[i])*int(fat[j])
        ls.append(a)
ls.sort(reverse=True)
print(ls[int(k)-1])
  • 正确率65%
发表于 2019-07-11 20:55:31 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;
int getCnt(vector<int>& v,LL val,LL k){
    LL cnt=0;
    bool flag = false;
    LL x = 0;
    for(int i = 1;i<v.size();i++){
        if(val<(LL)v[i]*v[0]) break;
        if(val>(LL)v[i]*v[i-1]){
            cnt=cnt+i;
            continue;
        }
        LL l = 0,r=i-1;
        while (l<r) {
            LL mid = l+r>>1;
            if((LL)v[i]*v[mid]>val){
                r=mid-1;
            }else if((LL)v[i]*v[mid]<val){
                l=mid+1;
            }else{
                flag=true;
                l=mid;
                break;
            }
        }
        while((LL)v[i]*v[l]==val && l<=r){
            flag=true;          
            x++;
            l++;
        }
        if((LL)v[l]*v[i]>val) l--;
        cnt=cnt+(l+1);
    }
    if(cnt<=k+x-1&&cnt>=k && flag){
        return 1;
    }else if(cnt>k||(cnt==k&&!flag)){
        return 0;
    }else{
        return 2;
    }
}
int main(){
    LL n,m;
    cin>>n>>m;
    vector<int> v(n);
    for(int i = 0;i<n;i++){
        scanf("%d",&v[i]);
    }
     sort(v.begin(),v.end());
     if(m==1){
        LL x = (LL)v[n-1]*v[n-2];
        cout<<x<<endl;
        exit(0);
    }
    LL l = (LL)v[0]*v[1],r=(LL)v[n-1]*v[n-2];
    LL k = n*(n-1)/2-m+1;
    while (l<r) {
        LL mid = (l+r)>>1;
        int val = getCnt(v, mid, k);
        if(val==1){
            cout<<mid<<endl;
            exit(0);
        }else if(val==0){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
}

编辑于 2019-06-14 22:03:37 回复(1)
public class Bilibili_sunwukong {
public static void main(String[] args) {
List<Integer> list=new LinkedList<>();

Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int[]a=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}

for(int i=0;i<a.length;i++){
for(int j=i+1;j<a.length;j++){
list.add(a[i]*a[j]);
}
}

Collections.sort(list);

System.out.println(list.get(list.size()-k));
}
通过率65%,说什么检查是否数组越界!!搞不懂哪里出问题了

编辑于 2019-05-14 16:57:11 回复(2)

热门推荐

通过挑战的用户

查看代码