Условие задачи
Есть 2N людей которым необходимо поехать в командировку. Стоимость полета для i-того сотрудника в город A равна costs[i][0], а стоимость полета для i-того сотрудника в город B равна costs[i][1].
Необходимо вернуть минимальную стоимость перелетов, с условием что каждый город посетить N человек.
пример 1
1
2
3
4
5
6
7
8
9
|
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
|
Ограничения
- 1 <=
len(costs) <= 100
- Гарантируется, что
len(costs) будет четной.
- 1 <=
costs[i][0], costs[i][1] <= 1000
Решение
Связный список
Считаем для каждого человека разницу между стоимостью путешествия в город A и город B. А потом добавляем в односвязный список это значение так, что бы список был отсортирован по возврастанию. А потом идем по получившемуся списку до середины – этих отправляем в город A, а всех остальных в город B
1
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
|
func twoCitySchedCost(costs [][]int) int {
st:= list{Val:-1}
for idx := range costs {
st.add(costs[idx][0],costs[idx][1], idx)
}
s:= 0
i:=0
stt := &st
for stt != nil {
i++
if i<=len(costs)/2{
s+=costs[stt.Idx][0]
} else {
s+=costs[stt.Idx][1]
}
stt = stt.Next
}
return s
}
type list struct {
Next *list
Val int
Idx int
}
func (v *list) add(vala, valb, idx int) {
if v.Val == -1 {
v.Val=vala-valb
v.Idx = idx
return
}
val := vala-valb
for v != nil {
if val <= v.Val {
ppp := *v
*v = list{
Val: val,
Idx:idx,
Next: &ppp,
}
return
}
if v.Next == nil && val > v.Val{
v.Next = &list{
Val: val,
Idx:idx,
}
return
}
v = v.Next
}
}
func (v *list) print(){
for v!= nil{
fmt.Println(v)
v = v.Next
}
}
|