50176. Bidding
難度：3.3/51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include <stdio.h>
#include <stdlib.h>
#include "bidding.h"
// typedef struct bid {
// int bidderID;
// int itemID;
// int bidPrice;
// } Bid;
//
// typedef struct itemMinPrice{
// int itemID;
// int minPrice;
// } ItemMinPrice;
typedef struct{
int bidder_id;
int item_id;
int bid_price;
int time;
int buy;
} helper;
helper new_bid[10005];
int cmp_helper(const void* aa, const void* bb){
helper* a = (helper*)aa;
helper* b = (helper*)bb;
if(a->item_id != b->item_id) return (a->item_id > b->item_id) ? 1 : -1;
if(a->bid_price != b->bid_price) return (a->bid_price > b->bid_price) ? -1 : 1;
return (a->time > b->time) ? 1 : -1;
}
int cmp_min_price(const void* aa, const void* bb){
ItemMinPrice* a = (ItemMinPrice*)aa;
ItemMinPrice* b = (ItemMinPrice*)bb;
return (a->itemID > b->itemID) ? 1 : -1;
}
int cmp_output(const void* aa, const void* bb){
helper* a = (helper*)aa;
helper* b = (helper*)bb;
if(a->buy && b->buy){
if(a->bidder_id != b->bidder_id) return (a->bidder_id > b->bidder_id) ? 1 : -1;
return (a->item_id > b->item_id) ? 1 : -1;
}
else{
if(a->buy) return -1;
if(b->buy) return 1;
return 1;
}
}
void get_new_bid(Bid bidSeq[], int m){
for(int i = 0; i < m; i++){
new_bid[i].bidder_id = bidSeq[i].bidderID;
new_bid[i].item_id = bidSeq[i].itemID;
new_bid[i].bid_price = bidSeq[i].bidPrice;
new_bid[i].time = i;
new_bid[i].buy = 0;
}
}
void bidding(Bid bidSeq[], int m, ItemMinPrice minPriceSeq[], int n){
get_new_bid(bidSeq, m);
qsort(new_bid, m, sizeof(helper), cmp_helper);
qsort(minPriceSeq, n, sizeof(ItemMinPrice), cmp_min_price);
int price_ptr = 0;
int last_item_id = -1;
for(int i = 0; i < m; i++){
if(new_bid[i].item_id == last_item_id) continue;
while(minPriceSeq[price_ptr].itemID != new_bid[i].item_id) price_ptr++;
if(new_bid[i].bid_price >= minPriceSeq[price_ptr].minPrice){
new_bid[i].buy = 1;
}
last_item_id = new_bid[i].item_id;
}
qsort(new_bid, m, sizeof(helper), cmp_output);
for(int i = 0; i < m; i++){
if(new_bid[i].buy == 0) break;
printf("Bidder %d gets item %d with %d dollars\n",
new_bid[i].bidder_id, new_bid[i].item_id, new_bid[i].bid_price);
}
}