微软面试题只有2%的人能回答

最近微软出了一到题目，据说只有2%的程序员答对了，什么题目呢，我们一起看看吧
题目描述：

在微软云计算服务的机房，有很多机器上跑着一个或者多个的虚拟机。在一段时间里，有很多用户会来请求建立虚拟机，或者把虚拟机关闭。这个时候，一个最重要的问题，是如何把用户的请求分配到不同的机器上。这里我们把实际的问题简化成对CPU的申请。

假定有M台机器用来服务用户，我们把机器编号成0到M。每台机器有多个CPU核，我们把核编号为0到Cm。

当用户在申请资源的时候，会生成一个请求 “申请<k>个核”，并且每个请求编号为m如果我们在现有的机器中能找到一台机器能满足，这台机器的空余的连续的核能满足要求的话，就返回<M, C>作为结果。M是机器的下标，C是申请的第一个核的下标。如果没有找到能满足请求的机器，<-1,

-1>作为结果。

当用户释放资源的时候，生成一个请求”第m个请求的资源释放”。保证一个请求释放最多一次。如果请求没有满足，忽略释放的请求。

输入
第一行是T, 总共的测试的个数
每个测试，第一行给出M 和Q，机器的总数和请求的个数
接下来是M行给出每一台机器的核数 Ci
接下来Q行给出请求。请求两种格式，
1.       A k    表示申请k个核
2.       F m   表示释放第m个请求申请的核
输出
对于每一个测试，首先输出
“Case #i:”  i是测试的标号，从1开始。
接下来对于所有申请的请求，输出m c 或者-1
-1
[限制条件]
1 <= T <= 20
1 <= M <= 100000
1 <= Ci <= 128
1 <= Q <= 1000000
1 <= k <= 128
1 <= m <= M
The number of queries of type 1 is the same
as that of type 2.

正确答案代码展示

1. #include <iostream> 
2. #include <cstdio> 
3. #include <vector> 
4. #include <set> 
5. #include <cstring> 
6.  
7. using namespace std; 
8. const int N = 100005; 
9. const int M = 130; 
10. const int inf = 1e9; 
11.  
12. struct Query{    //保存每一次询问的结果，id为机器编号，start为CPU起点，end为CPU终点 
13.     int id, start, end;     
14.     Query (){} 
15.     Query (int a, int b, int c):id(a), start (b), end (c){} 
16. }; 
17. bool a[N][M];        //记录每个机器CPU的使用情况 
18. int sz[N];            //记录每个机器CPU数 
19.  
20. /* 
21.  * 返回当前机器中连续num个空闲核的起点 
22.  */ 
23. int getStart (bool used[], int size, int num){ 
24.     int now = 0; 
25.     for (int i = 1; i <= size; i ++){ 
26.         if (!used[i]){ 
27.             now ++; 
28.             if (now == num){ 
29.                 return i - now + 1; 
30.             } 
31.         }else{ 
32.             now = 0; 
33.         } 
34.     } 
35.     return -1; 
36. } 
37.  
38. /* 
39.  * 返回当前机器最大连续空闲核的数量 
40.  */ 
41. int getMax (bool used[], int size){ 
42.     int maxx = 0; 
43.     int t = 0; 
44.     for (int i = 1; i <= size; i ++){ 
45.         if (!used[i]){ 
46.             t ++; 
47.             maxx = max (maxx, t); 
48.         }else{ 
49.             t = 0; 
50.         } 
51.     } 
52.     return maxx; 
53. } 
54.  
55. int main (){ 
56.     freopen ("1.txt", "r", stdin); 
57.     freopen ("3.txt", "w", stdout); 
58.     int T, cas = 1; 
59.     scanf ("%d", &T); 
60.     while (T --){ 
61.         memset (a, 0, sizeof (a)); 
62.         set<int> se[M];        //se[i]存储的是连续空闲数为i的所有机器编号 
63.         vector<Query> vec;    //保存历史询问 
64.         printf ("Case #%d:\n", cas ++); 
65.         int n, m; 
66.         scanf ("%d%d", &n, &m); 
67.         for (int i = 1; i <= n; i ++){ 
68.             scanf ("%d", sz + i); 
69.             se[sz[i]].insert (i); 
70.         } 
71.         while (m --){ 
72.             char op[5]; 
73.             int t; 
74.             scanf ("%s%d", op, &t); 
75.             if (op[0] == 'A'){ 
76.                 int id = inf; 
77.                 for (int i = t; i < M; i ++){ 
78.                     if (se[i].size ()){ 
79.                         id = min (id, *se[i].begin ()); 
80.                     } 
81.                 } 
82.                 if (id == inf){ 
83.                     puts ("-1 -1"); 
84.                     vec.push_back (Query (-1, -1, -1)); 
85.                 }else{ 
86.                     se[ getMax (a[id], sz[id]) ].erase (id); 
87.                     int start = getStart (a[id], sz[id], t); 
88.                     printf ("%d %d\n", id, start); 
89.                     for (int i = start; i <= start + t - 1; i ++){ 
90.                         a[id][i] = true; 
91.                     } 
92.                     vec.push_back (Query (id, start, start + t - 1)); 
93.                     se[ getMax (a[id], sz[id])].insert (id); 
94.                 } 
95.             }else{ 
96.                 t --; 
97.                 if (vec[t].id == -1)    continue; 
98.                 int id = vec[t].id; 
99.                 se[ getMax (a[id], sz[id]) ].erase (id); 
100.                 for (int i = vec[t].start; i <= vec[t].end; i ++){ 
101.                     a[id][i] = false; 
102.                 } 
103.                 se[ getMax (a[id], sz[id]) ].insert (id); 
104.             } 
105.         } 
106.     } 
107. }