[250 Points]

Problem Statement
You are given a String disk representing the clusters on a disk. An 'X' represents a used cluster, and a '.' represents an available cluster. You are also given an int size representing the size, in clusters, of a file waiting to be written to disk. A file can only be stored in clusters not already being used.
Return the minimum number of groups of consecutive clusters needed to store the file on the disk. (The disk does not wrap around at the end.) Return -1 if the disk does not have enough space available to store the file.
[译文]
问题陈述
给你一个字符串用来表示一个磁盘上的簇。一个'X'表示一个已经被使用过的簇，一个'.'表示一个可用的簇。同时给你一个整数，用来表示准备写入磁盘的文件大小(文件大小以簇为单位)。文件只能存放在没有被使用的簇上。
返回存放文件所需要的最少的连续簇的组数(磁盘不能回绕，解释：即不能把最后一个簇和第一个簇看作是连续的簇)。如果磁盘没有足够空间则返回-1。

Definition
Class: DiskClusters
Method: minimumFragmentation
Parameters: String, int
Returns: int
Method signature: int minimumFragmentation(String disk, int size)
(be sure your method is public)
[译文]
定义
类名: DiskClusters
函数名: minimumFragmentation
参数: String, int
返回值: int
函数原型: int minimumFragmentation(String disk, int size)

Constraints
-disk will contain between 1 and 50 characters, inclusive.
-Each character of disk will be 'X' or '.'.
-size will be between 1 and 50, inclusive.
[译文]
约束
-用来表示磁盘的字符串包括1至50个字符，含1和50。
-用来表示磁盘上的簇的字符必须是'X'或者'.'。
-准备存入磁盘的文件的大小在1至50之间，含1和50。

Examples
0)
"."
2
Returns: -1
We can't fit the file on the disk.

1)
".XXXXXXXX.XXXXXX.XX.X.X."
6
Returns: 6
There is only ever one cluster together, so all six clusters are separated.

2)
"XX..XX....X.XX........X...X.XX...XXXX..XX...XXXXX."
12
Returns: 2
We fit eight clusters together, and four clusters together.

3)
".X.XXXX.......XX....X.....X............XX.X.....X."
20
Returns: 3

4)
"....X...X..X"
11
Returns: -1

[译文]
举例
0)
"."
2
返回: -1
磁盘没有足够可用空间存放该文件。

1)
".XXXXXXXX.XXXXXX.XX.X.X."
6
返回: 6
只有6个可用的独立的簇，只有将这些簇合在一起才能存放该文件。

2)
"XX..XX....X.XX........X...X.XX...XXXX..XX...XXXXX."
12
Returns: 2
返回: 2
我们将一个含8个簇的块和一个含4个簇的块合在一起，能够容纳该需占用12个簇的文件。

3)
".X.XXXX.......XX....X.....X............XX.X.....X."
20
Returns: 3
返回: 3

4)
"....X...X..X"
11
Returns: -1
返回: -1

[解题思路]
遍历磁盘字符串，找出所有的可用簇块，然后排序。从最大的开始往下累加，当超过文件的大小，则返回簇块的个数，否则返回-1。

[参考答案如下]
以下代码在Windows Server 2003 Standard Edition SP1 , Borland C++ Builder 2006 Architech下运行通过。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class DiskClusters
{
public:
	int minimumFragmentation(string disk, int size);
};
//---------------------------------------------------------------------------

int DiskClusters::minimumFragmentation(string disk, int size)
{
    int i,j,k;
    vector <int> num;

    i=0;
    while((unsigned int)i<disk.length())
    {
        if(disk[i] == '.')
        {
            j=k=i;
            while(disk[i] == '.')
            {
                k++;
                i++;
            }
            if(disk[i] != '.')
            {
                num.push_back(k-j);
            }
        }
        else if(disk[i] == 'X')
        {
            i++;
        }
    }
    sort(num.begin(),num.end()); //从小到大排序
    j=0;
    k=0;
    for(i=num.size()-1; i>=0; i--)
    {
        j+=num[i];
        k++;
        if(j>=size) return k;
    }
    return -1;
}
//---------------------------------------------------------------------------

int main(int argc, char* argv[])
{
    DiskClusters test;
    string disk;
    int size;

    disk = ".";
    size = 2;
    cout<<"Examples: 0)"<<endl;
    cout<<"  disk:    "<<disk.c_str()<<endl;
    cout<<"  size:    "<<size<<endl;
    cout<<"  return:  "<<test.minimumFragmentation(disk,size)<<endl<<endl;

    disk = ".XXXXXXXX.XXXXXX.XX.X.X.";
    size = 6;
    cout<<"Examples: 1)"<<endl;
    cout<<"  disk:    "<<disk.c_str()<<endl;
    cout<<"  size:    "<<size<<endl;
    cout<<"  return:  "<<test.minimumFragmentation(disk,size)<<endl<<endl;

    disk = "XX..XX....X.XX........X...X.XX...XXXX..XX...XXXXX.";
    size = 12;
    cout<<"Examples: 2)"<<endl;
    cout<<"  disk:    "<<disk.c_str()<<endl;
    cout<<"  size:    "<<size<<endl;
    cout<<"  return:  "<<test.minimumFragmentation(disk,size)<<endl<<endl;

    disk = ".X.XXXX.......XX....X.....X............XX.X.....X.";
    size = 20;
    cout<<"Examples: 3)"<<endl;
    cout<<"  disk:    "<<disk.c_str()<<endl;
    cout<<"  size:    "<<size<<endl;
    cout<<"  return:  "<<test.minimumFragmentation(disk,size)<<endl<<endl;

    disk = "....X...X..X";
    size = 11;
    cout<<"Examples: 4)"<<endl;
    cout<<"  disk:    "<<disk.c_str()<<endl;
    cout<<"  size:    "<<size<<endl;
    cout<<"  return:  "<<test.minimumFragmentation(disk,size)<<endl<<endl;

    cin.get();
    return 0;
}