首页 > 试题广场 >

赏金猎人

[编程题]赏金猎人

热度指数：1493 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

西部世界中有 $\mathit n$ 个赏金猎人，每个赏金猎人都有两个属性战斗力和所拥有金钱。( $\mathit attack[i],money[i]$ 分别表示第 $\mathit i$ 个赏金猎人的战斗力和所拥有金钱，保证每个赏金猎人的战斗力不相同)。每一个赏金猎人只有 $\mathit k$ 发子弹，这意味着他最多可以击败 $\mathit k$ 个战斗力比他小的赏金猎人并获取他们的金钱。你能输出每一个赏金猎人最多拥有多少金钱

输入描述:

第一行包含两个整数。
第二行包含个整数。
第三行包含个整数。

输出描述:

输出一行包含个整数，第个整数表示第个赏金猎人最多拥有金钱数。

示例1

输入

3 1
1 8 3
1 8 5

输出

1 13 6

说明

第一个猎人战斗力只有1，不能击败任何人。第二个猎人可以击败第三个猎人，因此他的金钱为13。第三个猎人可以击败第一个猎人，所以他的金钱为6。

算法知识视频讲解

pein531

贪心+小根堆

先按照赏金猎人的攻击力升序排列。然后遍历赏金猎人数组，构建一个容量为k的小根堆（存放当前赏金猎人能PK过的对手中，最有钱的topk），从攻击力小的赏金猎人开始计算，当前赏金猎人能够得到的资金为他自己的资金+堆中的资金总和。

import java.io.*;
import java.util.*;

class Hunter {
    public int id;
    public int attack;
    public int money;
    public Hunter(int i, int attack) {
        this.id = i;
        this.attack = attack;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int k = Integer.parseInt(params[1]);
        Hunter[] hunter = new Hunter[n];
        params = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            hunter[i] = new Hunter(i, Integer.parseInt(params[i]));
        }
        params = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            hunter[i].money = Integer.parseInt(params[i]);
        }
        // 所有赏金猎人按照攻击力升序排列
        Arrays.sort(hunter, (h1, h2) -> h1.attack - h2.attack);
        // 建立一个按钱升序排列且容量为k的小根堆，用来存储每个赏金猎人能干掉的对手中钱最多的topk
        PriorityQueue<Hunter> minHeap = new PriorityQueue<>((h1, h2) -> h1.money - h2.money);
        int[] res = new int[n];
        int moneyInHeap = 0;    // 堆中的钱数，堆中放当前赏金猎人能pk过的对手中，钱最多的topk的资金总和
        // 为了能够累加前面的结果，从攻击力小的赏金猎人开始计算
        for(int i = 0; i < n; i++){
            res[hunter[i].id] = hunter[i].money + moneyInHeap;
            if(minHeap.size() < k){
                moneyInHeap += hunter[i].money;
                minHeap.offer(hunter[i]);
            }else{
                if(minHeap.peek().money < hunter[i].money){
                    moneyInHeap -= minHeap.poll().money;
                    minHeap.offer(hunter[i]);
                    moneyInHeap += hunter[i].money;
                }
            }
        }
        for(int i = 0; i < n; i++){
            System.out.print(res[i] + " ");
        }
    }
}

发表于 2022-01-22 19:38:12 回复(0)

onceday

*****纯C代码实现********

此题关键在于排序算法的复杂度，attack是必须要排序的，而money可以取巧。

将attack按照从小到大升序排列，按照递归思想，如果a的战斗力比b大，那么

b的最大sum_money=a->sum_money(max)-min(a->sum_money(0),,,a->sum_money(k-1),a->money)+b->money;

即在a的k个击败序列中剔除比a自身money小的单位（如果有的话），整体上复杂度k*n（采用有序插入排序）。

attack的排序在n达到10^4数量级时，普通的n^2复杂度算法将无法满足需求，需要采用n*log(n)复杂度算法。

下面的代码有三种排序，归并排序（复杂度低）---O(nlogn);冒泡排序，选择排序--O(n^2)。全部代码实现。

#include "stdio.h"
#include "stdlib.h"

typedef struct __list
{
int id;
int attack;
int money;
struct __list* next;
}_list;

void get_attack(_list* list);
void get_attack1(_list* list);
void get_money(_list* list);
void sort(_list* list, _list* list2);
void deal(_list* list, long long int* max, int k);
void sort_1(_list* list);
_list** sort3(_list* slist1[100000], _list* slist2[100000], _list* olist, int num);
void deal2(_list** list, long long int* max, int num, int k);
_list* slist11[100000];
_list* slist22[100000];

int main(void)
{
int n = 0;
int k = 0;
_list list;
_list list1[100000];
long long int max[100000];
_list** slist3 = NULL;
scanf("%d %d", &n, &k);
getchar();
list.next = list1;
get_attack1(list.next);
get_money(list.next);
list.next->next = NULL;
if(n>20000)
{
slist3 = sort3(slist11, slist22, list1, n);
deal2(slist3, max, n, k);
}
else
{
for(int i=1;i<n;i++)
sort(&list,list1+i);
deal(&list,max,k);
}
for (int i = 0; i < n; i++)
{
printf("%lld ", max[i]);
}
printf("\n");
system("pause");
}
void deal2(_list** list, long long int* max, int num, int k)
{
long long int money[11];
long long int temp = 0;
int pos = 0;
money[0] = 0;
money[1] = list[0]->money;
money[0] += money[1];
max[list[0]->id] = money[0];
pos = 1;
for (int i = 2; i <= k; i++)
{
temp = list[pos]->money;
money[0] += temp;
max[list[pos]->id] = money[0];
for (int j = i - 1; j > 0; j--)
{
if (temp > money[j])
{
money[j + 1] = money[j];
}
else
{
money[j + 1] = temp;
break;
}
}
if (temp > money[1])
money[1] = temp;
pos++;
}
while (pos < num)
{
temp = list[pos]->money;
max[list[pos]->id] = money[0] + temp;
if (temp > money[k])
{
money[0] += temp - money[k];
for (int i = k - 1; i > 0; i--)
{
if (temp > money[i])
{
money[i + 1] = money[i];
}
else
{
money[i + 1] = temp;
break;
}
}
if (temp > money[1])
money[1] = temp;
}
pos++;
}
}
void deal(_list* list, long long int* max, int k)
{
_list* list1 = list->next;
long long int* money = NULL;
long long int temp = 0;
money = (long long int*)malloc((k + 1) * sizeof(long long int));
money[0] = 0;
money[1] = list1->money;
money[0] += money[1];
max[list1->id] = money[0];
list1 = list1->next;
for (int i = 2; i <= k; i++)
{
temp = list1->money;
money[0] += temp;
max[list1->id] = money[0];
for (int j = i - 1; j > 0; j--)
{
if (temp > money[j])
{
money[j + 1] = money[j];
}
else
{
money[j + 1] = temp;
break;
}
}
if (temp > money[1])
money[1] = temp;
list1 = list1->next;
}
while (list1 != NULL)
{
temp = list1->money;
max[list1->id] = money[0] + temp;
if (temp > money[k])
{
money[0] += temp - money[k];
for (int i = k - 1; i > 0; i--)
{
if (temp > money[i])
{
money[i + 1] = money[i];
}
else
{
money[i + 1] = temp;
break;
}
}
if (temp > money[1])
money[1] = temp;
}
list1 = list1->next;
}
}

_list** sort3(_list* slist1[100000] , _list* slist2[100000], _list* olist, int num)
{
int temp = 2;
int temp2 = temp >> 1;
int temp3 = temp >> 1;
int i = 0, j = 0, z = 0;
_list** slist3 = NULL;
_list** slist4 = NULL;
_list** slist5 = slist1;

while (1)
{
i += temp;
if (i <= num)
{
j = i - 2, z = i - 1;
if (olist[j].attack < olist[z].attack)
{
*(slist5++) = olist + j;
*(slist5++) = olist + z;
}
else
{
*(slist5++) = olist + z;
*(slist5++) = olist + j;
}
}
else
{
if (i == num+1)
*(slist5) = olist + num - 1;
break;
}
}
slist5 = slist2;
i = 0;
while (1)
{
while (1)
{
slist3 = slist1 + i;
i += temp;
if (i < num )
temp2 = temp;
else
{
temp2 = temp - (i - num );
j = 0;
while (j < temp2)
{
*(slist5++) = slist3[j++];
}
break;
}
slist4 = slist3 + temp2;
i += temp;
if (i < num)
temp3 = temp;
else
{
temp3 = temp - (i - num );
}
j = 0, z = 0;
while (j < temp2 && z < temp3)
{
if (slist3[j]->attack < slist4[z]->attack)
{
*(slist5++) = slist3[j++];
}
else
{
*(slist5++) = slist4[z++];
}
}
while (j < temp2)
{
*(slist5++) = slist3[j++];
}
while (z < temp3)
{
*(slist5++) = slist4[z++];
}
}
i = 0;
temp *= 2;
if (temp > num)
{
slist5 = slist2;
break;
}
slist5 = slist1;
while (1)
{
slist3 = slist2 + i;
i += temp;
if (i < num )
temp2 = temp;
else
{
temp2 = temp - (i - num );
j = 0;
while (j < temp2)
{
*(slist5++) = slist3[j++];
}
break;
}
slist4 = slist3 + temp2;
i += temp;
if (i < num)
temp3 = temp;
else
{
temp3 = temp - (i - num);
}
j = 0, z = 0;
while (j < temp2 && z < temp3)
{
if (slist3[j]->attack < slist4[z]->attack)
{
*(slist5++) = slist3[j++];
}
else
{
*(slist5++) = slist4[z++];
}
}
while (j < temp2)
{
*(slist5++) = slist3[j++];
}
while (z < temp3)
{
*(slist5++) = slist4[z++];
}
}
i = 0;
temp *= 2;
if (temp > num)
{
slist5 = slist1;
break;
}
slist5 = slist2;
}
return slist5;
}

void sort(_list* list, _list* list2)
{
_list* list1 = list->next;
while (list1 != NULL)
{
if (list1->attack < list2->attack)
{
list = list1;
list1 = list1->next;
}
else
{
list->next = list2;
list2->next = list1;
break;
}
}
if (list1 == NULL)
{
list->next = list2;
list2->next = NULL;
}
}

void sort_1(_list* list)
{
int flag = 1;
_list* olist = list;
_list* list1 = list->next;
_list* list2 = list1->next;
while (flag)
{
flag = 0;
while (list2 != NULL)
{
if (list1->attack > list2->attack)
{
flag = 1;
list->next = list2;
list1->next = list2->next;
list2->next = list1;
list = list2;
list2 = list1->next;
}
else
{
list = list1;
list1 = list2;
list2 = list2->next;
}
}
list = olist;
list1 = list->next;
list2 = list1->next;
}
}
void get_money(_list* list)
{
char temp = getchar();
long int sum = 0;
while (1)
{
if (temp >= '0')
{
sum = sum * 10 + temp - '0';
}
else if (temp != '\n')
{
list->money = sum;
sum = 0;
list++;
}
else
{
break;
}
temp = getchar();
}
list->money = sum;
}
void get_attack(_list* list)
{
char temp = getchar();
long int sum = 0;
int id = 0;
while (1)
{
if (temp >= '0')
{
sum = sum * 10 + temp - '0';
}
else if (temp != '\n')
{
list->id = id++;
list->attack = sum;
list->next = list + 1;
sum = 0;
list++;
}
else
{
break;
}
temp = getchar();
}
list->id = id;
list->attack = sum;
list->next = NULL;
}
void get_attack1(_list* list)
{
char temp = getchar();
long int sum = 0;
int id = 0;
while (1)
{
if (temp >= '0')
{
sum = sum * 10 + temp - '0';
}
else if (temp != '\n')
{
list->id = id++;
list->attack = sum;
sum = 0;
list++;
}
else
{
break;
}
temp = getchar();
}
list->id = id;
list->attack = sum;
}

编辑于 2021-09-27 18:16:25 回复(0)

黑莓婆婆

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int> > arr(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        arr[i][2] = i;  // 记录编号
        cin >> arr[i][0];  // 输入attack
    }
    for (int i = 0; i < n; i++) {
        cin >> arr[i][1];  // 输入money
    }
    sort(arr.begin(), arr.end());  // 按战斗力排序
    int sum = 0;
    vector<int> res(n);
    priority_queue<int, vector<int>, greater<int> > Q;
    for (auto& it : arr) {  // 后面的肯定能战胜前面所有的
        int money = it[1], i = it[2];
        sum += money;
        res[i] = sum;
        Q.push(money);
        if (Q.size() > k) {
            sum -= Q.top();
            Q.pop();
        }
    }
    for (auto x : res) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

按attack值排序，小于它的肯定可以被他打败，再设置一个大小为k的优先队列即可。

发表于 2021-07-16 19:56:17 回复(0)

谦虚的你希望被offer砸中

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();

Hunter[] hunters=new Hunter[n];
for (int i = 0; i < n; i++) {
hunters[i]=new Hunter();
hunters[i].attack=sc.nextInt();
hunters[i].index=i;
}
for (int i = 0; i < n; i++) {
hunters[i].money=sc.nextInt();
}

//按照赏金建立小顶堆
PriorityQueue<Hunter> pq=new PriorityQueue<>(new Comparator<Hunter>() {
@Override
public int compare(Hunter o1, Hunter o2) {
return o1.money- o2.money;
}
});

//首先按照攻击力进行排序
Arrays.sort(hunters, new Comparator<Hunter>() {
@Override
public int compare(Hunter o1, Hunter o2) {
return o1.attack-o2.attack;
}
});
//计算结果
int[] res=new int[n];
int sum=0;
for (int i = 0; i < n; i++) {
int money=hunters[i].money;
sum += money;
//原本的位置添加
res[hunters[i].index]=sum;
pq.offer(hunters[i]);
if(pq.size()>k){
//减去其中的最小值,并取出
sum -= pq.peek().money;
pq.poll();
}
}

//输出结果
for (int re : res) {
System.out.print(re+" ");
}
}

}

class Hunter{
public int attack;
public int money;
public int index;
}

发表于 2021-07-23 20:06:47 回复(0)

C/C++

你会发光ii

#include <bits/stdc++.h>
using namespace std;

struct hunter
{
    int atk, m, idx;
};


int main() {
    // n个人，每人k发子弹
    int n, k; cin >> n >> k;
    vector<int> attack(n);
    vector<int> money(n);
    for(int i = 0; i < n; i++) {
        cin >> attack[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> money[i];
    }
    // 初始化结构体
    hunter hs[n];
    for(int i = 0; i < n; i++) {
        hs[i] = { .atk = attack[i], .m = money[i], .idx = i };
    }
    // 释放内存
    vector<int>().swap(attack);
    vector<int>().swap(money);
    sort(hs, hs + n, [&](hunter a, hunter b) {return a.atk < b.atk;});

    vector<int> res(n);
    int curr_sum = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i = 0; i < n; i++) {
        res[hs[i].idx] = hs[i].m;
        if(i != 0) {
            int _idx = i - 1;
            if(q.size() < k) {
                curr_sum += hs[_idx].m;
                q.push(hs[_idx].m);
            }
            else if(k > 0 && hs[_idx].m > q.top()) {
                curr_sum = curr_sum - q.top() + hs[_idx].m;
                q.pop();
                q.push(hs[_idx].m);
            }
            res[hs[i].idx] += curr_sum;
        }
    }
    cout << res[0];
    for(int i = 1; i < n; i++) {
        cout << " " << res[i];
    }
    return 0;
}

发表于 2021-07-15 11:30:43 回复(0)

做一个努力学习的奋斗者

按照战斗力先正序排序，然后第i位的战斗力可以获取的金额两种情况：

当i<=k的时候：moneysum （i）= moneysum (i-1) + money(i);

当i>k的时候：moneysum （i）= moneysum (i-1) + money(i) - 减去k个中金额最低哪一位;

import java.util.*;
public class Main {
         public static void main(String[]args){
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            String[] str = s.split(" ");
            int n = Integer.parseInt(str[0]);
            int k = Integer.parseInt(str[1]);
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();
            String[] str1 = s1.split(" ");
            String[] str2 = s2.split(" ");
            //int[] attack = new int[n];
            //int[] money = new int[n];
            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            for(int i=0;i<n;i++){
                ArrayList<Integer> list0 = new ArrayList<>();
                list0.add(Integer.parseInt(str1[i]));
                list0.add(Integer.parseInt(str2[i]));
                list.add(list0);
            }
            //ArrayList<ArrayList<Integer>> old = list;
            //System.out.println(old);
            //按照战斗力排序,正序
            Collections.sort(list,new Comparator<ArrayList<Integer>>(){
                public int compare(ArrayList<Integer> o1,ArrayList<Integer> o2){
                    return o1.get(0)-o2.get(0);
                }
            });
            HashMap<ArrayList<Integer>,Integer> map = new HashMap<>();
            int money = 0;
            //记录money排序，正序排序
            ArrayList<ArrayList<Integer>> moneynum = new ArrayList<>();
            for(int i=0;i<list.size();i++){
                //需要考虑k发子弹是否超过人数，攻击力最低一个可能一发子弹一个都打出去
                if(i<=k) {
                	money = money + list.get(i).get(1);
                	moneynum.add(list.get(i));
                }else if(i>k) {
                	money = list.get(i).get(1) + map.get(list.get(i-1))-moneynum.get(0).get(1);
                	//去除最低的金额的
                    moneynum.remove(0);
                    //将当前金额加入集合
                	moneynum.add(list.get(i));
                }
                map.put(list.get(i),money);
                //金额排序，方便下一次计算
                 Collections.sort(moneynum,new Comparator<ArrayList<Integer>>(){
                   public int compare(ArrayList<Integer> o1,ArrayList<Integer> o2){
                    return o1.get(1)-o2.get(1);
                }
               });
            }
            //打印
            for(int i=0;i<n;i++){
                ArrayList<Integer> list0 = new ArrayList<>();
                list0.add(Integer.parseInt(str1[i]));
                list0.add(Integer.parseInt(str2[i]));
                if(i<n-1){
                    System.out.print(map.get(list0)+" ");
                }else{
                    System.out.print(map.get(list0));
                }
            }
        }
}

发表于 2022-02-19 17:39:52 回复(0)

牛客874379253号

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
m=[int(i) for i in input().split()]
a_s=sorted(a)
m_s=sorted(m)
o=[0 for i in range(n)]
for i,att in enumerate(a_s):
ind=a.index(att)
if i<k:
kill_lst=a_s[:i]
money=m[ind]
for ele in kill_lst:
money+=m[a.index(ele)]
o[skt]=money
else:
kill_lst=a_s[:i]
money=[0 for j in range(i)]
for l,ele in enumerate (kill_lst):
money[l]=m[a.index(ele)]
money=sorted(money,reverse=True)
to_m=m[ind]
for mon in money[:k]:
to_m+=mon
o[ind]=to_m
for i in o:
print(i,end=' ')

超时1/3

发表于 2021-11-14 22:15:31 回复(0)

谁能给我个offer啊

输出设置***啊

发表于 2021-08-08 10:24:36 回复(2)

牛客479854335号

import java.util.*;
//HashMap+ArrayList+自然排序+定制排序，用例全部通过，只是时间略微有点长
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        String s = input.nextLine();
        String[] arr = s.split(" ");
        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);
        if (k > 10) {
            k = 10;
        }

        String s1 = input.nextLine();

        String s2 = input.nextLine();
        String[] arr1 = s1.split(" ");
        String[] arr2 = s2.split(" ");

        long[] money = new long[n];

        //定制排序
        TreeSet<Hunter> set = new TreeSet(new Comparator<Hunter>(){
            @Override
            public int compare(Hunter o1, Hunter o2) {
                if(o1.attack > o2.attack){
                    return -1;
                }
                if(o1.attack < o2.attack){
                    return 1;
                }
                if (o1.attack == o2.attack){
                    return 0;
                }
                return 0;
            }
        });

        List<Hunter> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            money[i] = Long.valueOf(arr2[i]);
            Hunter hunter = new Hunter(i, Long.valueOf(arr1[i]), Long.valueOf(arr2[i]));
            set.add(hunter);
            list.add(hunter);
        }

        //自然排序
        Collections.sort(list);


        long countMoney;
        Iterator<Hunter> iterator = set.iterator();

        for(int i = 0;i < set.size() - 1;i++){
            Hunter h = iterator.next();
            countMoney = money[h.index];
            int count = 0;
            for (Hunter h1 : list) {
                if(h.attack > h1.attack){
                    countMoney += h1.money;
                    count++;
                }
                if(count >= k){
                    break;
                }
            }
            money[h.index] = countMoney;
        }

        for(int i = 0;i < n;i++){
            System.out.print(money[i]);
            if(i < n - 1){
                System.out.print(" ");
            }
        }

    }

    static class Hunter implements Comparable<Hunter>{
        public int index;
        public long attack;
        public long money;

        public Hunter(int index, long attack, long money) {
            this.index = index;
            this.attack = attack;
            this.money = money;
        }
        @Override
        public int compareTo(Hunter o) {
            if(this.money > o.money){
                return -1;
            }
            if(this.money < o.money){
                return 1;
            }
            if (this.money == o.money){
                return 0;
            }
            return 0;
        }
    }

}

发表于 2021-08-07 15:18:54 回复(0)

头文字F

部分测试用例通不过，希望哪位仁兄可以指点！！！！

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main(){
    int n, k;
    vector<int> av;
    map<int, int, greater<int>> hm;
    cin>>n>>k;
    for(int i=0; i<n; i++){
        int curNum;
        cin>>curNum;
        av.push_back(curNum);
    }
    for(int i=0; i<n; i++){
        int curNum;
        cin>>curNum;
        hm.insert(pair<int, int>(av[i], curNum));
    }
    for(int i=0; i<n; i++){
        int curA = av[i];
        auto iter = hm.find(curA);
        int tmpK = k;
        long curScore = iter->second;
        while(++iter != hm.end() && tmpK-- > 0){
            if(iter->first < curA){
                curScore += iter->second;
            }
        }
        cout<<curScore<<" ";
    }  
    return 0;
}

发表于 2021-08-03 18:35:20 回复(0)

天涯叹雪

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
 
int main() {
    int n, k;
    while (cin >> n >> k) {
        unordered_map<int, int> hash;
        vector<int> attack;
        int money[100001];
        long res[100001];
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            attack.push_back(tmp);
            hash[tmp] = i;
        }
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            money[i] = tmp;
            res[i] = tmp;
        }
        sort(attack.begin(), attack.end());
        priority_queue<int, vector<int>, greater<int>> q;
        int sum = 0;
        if (k > 0) {
            for (int i = 1; i < n; i++) {
                if (q.size() < k) {
                    q.push(money[hash[attack[i - 1]]]);
                    sum += money[hash[attack[i - 1]]];
                }
                else if (money[hash[attack[i - 1]]] > q.top()) {
                    sum -= q.top();
                    q.pop();
                    q.push(money[hash[attack[i - 1]]]);
                    sum += money[hash[attack[i - 1]]];
                }
                res[hash[attack[i]]] += sum;
            }
        }
        for (int i = 0; i < n - 1; i++) cout << res[i] << ' ';
        cout << res[n - 1] << endl;
    }
    return 0;
}

发表于 2021-07-21 17:24:11 回复(0)

牛客527764874号

n, k = [int(n) for n in input().split(' ')]
attack, money = [int(n) for n in input().split(' ')], [int(n) for n in input().split(' ')]
rank = sorted(attack, reverse=True)
index = [attack.index(at) for at in rank]
result = []
for i in range(n):
    ranking = rank.index(attack[i])
    can_kill = n - ranking - 1
    if can_kill >= k:
        result.append(str(sum([money[n] for n in index[ranking:ranking + k + 1]])))
    else:
        result.append(str(sum([money[n] for n in index[ranking:]])))
print(' '.join(result))

发表于 2021-07-19 02:21:35 回复(1)

23届-谭江晓

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5+5;

struct node{
    int stack;
    int money;
    int idx;
}arr[N];

int n,k;
vector<int> res;

bool cmp(struct node a , struct node b){
    return a.stack < b.stack;
}
int main(){
    cin>>n>>k;
    res = vector<int>(n);
    for(int i = 0; i < n ;i++) cin>>arr[i].stack;
    
    for(int i = 0; i < n ;i++){
        cin>>arr[i].money;
        arr[i].idx = i;
    }
    
    sort(arr, arr+n,cmp);
    
    //for(int i = 0; i < n ;i++) cout<<arr[i].stack<<" "<<arr[i].money<<endl;
    priority_queue<int,vector<int>,greater<int>> q;
    int s = 0;
    
    for(int i = 0 ; i < n ; i++){
        int money = arr[i].money;
        int idx = arr[i].idx;
        s+=money;
        res[idx] = s;
        q.push(money);
        if(q.size() > k) {
            s = s-q.top();
            q.pop();
        }
    }
    for(int x : res) cout<<x<<" ";
}

发表于 2021-07-17 13:36:42 回复(0)

牛客346892706号

n, k = 3, 1

attack = [1,8,3]

money = [1,8,5]

for ind in range(n):

dic = dict(zip(attack, money))

att = list(dic.keys())

mo = []

att.sort()

i = att.index(attack[ind])

for j in att[0:i]:

mo.append(dic[j])

mo.sort(reverse=True)

summ = money[ind] + sum(mo[:k])

print(summ, end=' ')

发表于 2021-07-14 15:00:26 回复(1)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师 Java工程师牛客

上传者：小小

难度：

14条回答 54收藏 3311浏览

通过挑战的用户

徐一sehun

2022-11-12 16:01:44
牛客51925...

2022-11-04 14:59:58
SpRiseMax

2022-10-11 11:16:09
960321168

2022-10-06 13:26:34
糸纪

2022-09-21 18:39:44