小美的跑腿代购

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

typedef struct Node {
	int id;
	int income;
	Node() {}
	Node(int id, int v, int w) {
		this->id = id;
		income = v + (w * 2);
	}
}node;

bool cmp(node x,node y) {
	if (x.income == y.income) return x.id < y.id;  //收入相等，编号从小到大
	return x.income > y.income;	//收入不相等，收入从大到小 
}

int main() {
	int n, m;
	cin >> n >> m;

	vector<node> goods(n);

	int v = 0, w = 0;
	for (int i = 0; i < n; i++) {
		cin >> v >> w;
		goods[i] = Node(i + 1, v, w);
	}

	sort(goods.begin(), goods.end(), cmp);
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < m; i++) {
		pq.push(goods[i].id);
	}

	for (int i = 0; ; i++) {
		if (i == m) break;
		cout << pq.top() << " ";
		pq.pop();
	}

	return 0;
}

const [n, m] = readline().split(' ').map(Number)
let value = new Array(n).fill(0)
for(let i = 0; i < n; i++) {
    const [v, w] = readline().split(' ').map(Number)
    value[i] = {value: v + w * 2, index: i}
}
value = value.sort((a, b) => { // 对不同订单的收入进行从大到小的排序
    if(b.value !== a.value) {
        return b.value - a.value // 收入不同, 收入从大到小
    }else {
        return a.index - b.index // 收入相同, 编号从小到大
    }
})
const ans = new Array(m)
for(let i = 0; i < m; i++) {
    ans[i] = value[i].index + 1
}
console.log(ans.sort((a, b) => a - b).join(' '))

#include<bits/stdc++.h>

using namespace std;

const int N = 50005;
const int M = 50005;

int v[N];
int w[N];
int flag[M];
int ans[M];
//int allsum[N];

bool cmp(pair<int,int>& a,pair<int,int> &b){
    if(a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

vector<pair<int,int>>good;

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        cin >> v[i]>>w[i];
    }
    int cnt = 0;
    vector<pair<int,int>>good;
    priority_queue<int,vector<int>,greater<int>>que;
    for(int i = 0;i < n;i++){
       int  allsum = v[i] + 2 * w[i];
        good.push_back(make_pair(allsum,i));
    }

     sort(good.begin(),good.end(),cmp);
     for(int i = n - 1; i > n - 1 - m;i--){
         ans[n - 1 - i] = good[i].second  + 1;
    }
     sort(ans,ans + m);
    for(int i = 0 ;i < m;i++){
      i!= 0&& cout << " ";
        cout << ans[i] ;
     }
    return 0;
}

n, m = list(map(int, input().split()))

import heapq
heap = []
hashmap = {}
for i in range(m):
    pair = list(map(int, input().split()))
    heapq.heappush(heap, pair[0]+pair[1]*2)
    if pair[0]+pair[1]*2 not in hashmap:
        hashmap[pair[0]+pair[1]*2] = [i+1]
    else:
        hashmap[pair[0]+pair[1]*2] += [i+1]
for i in range(m, n):
    pair = list(map(int, input().split()))
    if pair[0]+pair[1]*2 > heap[0]:
        if len(hashmap[heap[0]]) == 1:
            hashmap.pop(heap[0])
        else:
            hashmap[heap[0]].pop()
        if pair[0]+pair[1]*2 not in hashmap:
            hashmap[pair[0]+pair[1]*2] = [i+1]
        else:
            hashmap[pair[0]+pair[1]*2] += [i+1]
        heapq.heapreplace(heap, pair[0]+pair[1]*2)
re = []
for j in hashmap.values():
    re += j
re.sort()
print(" ".join(map(str, re)))

TOP K 最小堆

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

public class Solution {
    public static void main(String[] args) {
        //输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] v = new int[n], w = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        //最小堆（价值升序 序号降序）
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        //PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < n; i++) {
            //价值
            int val = v[i] + 2 * w[i];
            if (minHeap.size() < m) {
                minHeap.offer(new int[]{val, i + 1});
            } else {
                //最小堆 堆顶元素
                int[] T = minHeap.peek();
                if (T[0] < val) {
                    minHeap.poll();
                    minHeap.offer(new int[]{val, i + 1});
                }
                //此处省略了判断T[0]==val&&i<T[1]情况，因为i逐步增大，那么最小堆中的T[k]值必然小于i值
            }
        }

        //输出
        int[] res = new int[m];
        int idx = 0;
        while (!minHeap.isEmpty()) {
            res[idx++] = minHeap.poll()[1];
        }
        //快排
        Arrays.sort(res);
        for (int i = 0; i < m; i++) {
            System.out.printf(String.valueOf(res[i]));
            if (i != m) {
                System.out.printf(" ");
            }
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int orderNum=sc.nextInt();
        int orderNumAccept=sc.nextInt();
        PriorityQueue<Order> minPQ=new PriorityQueue<>(orderNumAccept+1,(order1,order2)->{
            if(order1.money!=order2.money)
                return order1.money-order2.money;
            else
                return order2.id-order1.id;
        });
        for(int i=1;i<=orderNum;++i){
            int part1=sc.nextInt();
            int part2=sc.nextInt()*2;
            Order order=new Order(i,part1+part2);
            minPQ.add(order);
            if(minPQ.size()>orderNumAccept)
                minPQ.remove();
        }
        ArrayList<Integer> orderIds=new ArrayList<>();
        for(Order order:minPQ)
            orderIds.add(order.id);
        Collections.sort(orderIds);
        for(Integer id:orderIds)
            System.out.print(id+" ");
    }
}
class Order{
    int id;
    int money;
    public Order(int id,int money){
        this.id=id;
        this.money=money;
    }
}