尘埃落定！值得纪念的一刻

and.. Goodbye, Microsoft，微软大法好！

题目

原题：http://hihocoder.com/problemset/problem/1137?sid=476594

大意是：

有N个应聘者，分别知道他们的价值V，期望薪水S，以及性别。招聘要求是：男X名，女Y名，总预算B（即期望薪水之和不能超过B），如何使总价值最大？

题目

看完了《背包九讲》，找个OJ练练手。

原题参考： http://poj.org/problem?id=1276

大意是：一个取款机有N种钞票，每种钞票有n[k]张，面额为D[k]，给定一个取款金额cash，可行的、不超过该金额的吐钞方案是多少钱？

题目来源

题目： http://hihocoder.com/problemset/problem/1136

前几天Google onsite面试，已挂。今天仔细思考了面试中一道没写出来的题，发现也并不难。诶，只能怪当时脑抽了。

题目大意

给定一个巨大的无序数组，输出数组中出现次数最多的K个数。

函数说明

参数都是一样的：

make_heap(first ,last)
make_heap(first ,last, cmpObject)

将[first, last)范围进行堆排序，默认使用less<int>, 即最大元素放在第一个。

pop_heap(first ,last)
pop_heap(first ,last, cmpObject)

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

题解

这题看似很简单，但是务必考虑如下情形：

时间复杂度最低的方法是，修改归并排序（Merge Sort），在排序同时对逆序对计数。时间复杂度为 \(O(n\log{n})\)。

C99 inline semantics are often misunderstood. The inline specifier serves two purposes:

First, as a compiler hint in case of static inline and extern inline declarations. Semantics remain unchanged if you remove the specifier.

Second, in case of raw inline (ie without static or extern) to provide an inline definition as an alternative to an external one, which has to be present in a different translation unit. Not providing the external one is undefined behaviour, which will normally manifest as linking failure.

写过C程序都知道，malloc了新的struct之后，经常跟着一大串的赋值。其实这些可以用一行漂亮的代码搞定。

先上代码：

1
2
3
4

#define new(type, ...) ({\
       type* __t = (type*) malloc(sizeof(type));\
       *__t = (type){__VA_ARGS__};\
       __t; })