微軟面試題只有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. }