Bamboo的OS实验#
分析##
首先理解题意，要完成不同数量的不同命令，但是完成相同的命令之间必须有n个间隔，为使得时间最短，自然优先用其他命令来填充这n分钟的时间，由于数量少的命令可以用来填充空隙，所以次数最多的命令是起作用最大的。而且注意到，每次具体执行的是哪个命令并不影响时间，只与命令的数量有关（这有点贪心的思想，当预习吧）
基于以上分析，可以有以下几种方法：
1、按照命令数量从大到小排列，每次都是从数量最多的命令开始新一轮周期，这样是用时最少的。
举个栗子，命令1 2 3 4 5各有6 1 1 1 1个，n=2，如果采用 1->2->3->4->5->1_->..这样就会导致数量最多的命令1每个都要有2个空的时间段来填充；最佳的思想是1->2->3->1->4->5,这样尚未进入周期的命令1才需要额外的时间填充。
那么，将命令按数量从大到小排列后，总是选择当前数量最多的开始一轮周期，对选择的命令数量-1，时间++；每次这个周期一旦开始就要开始记录是否到n,周期结束后，要重新排序以保证从大到小的顺序，直到最多的命令也执行完毕，后面无需时间填充
核心代码如下：
static bool cmp(int i, int j)
{
return i>j;
}
int Map[35];
int main()
{
int c,n,x;
while(~scanf("%d",&x))
{
for(int i=0; i<35; i++)Map[i]=0;
for(int i = 0; i<x; i++)
{
cin>>c;
Map[c]++;
}
scanf("%d",&n);
sort(Map,Map+35,cmp);
int time = 0;
while(Map[0]!=0)
{
int k =0;
while(k<=n)
{
if(k<31&&Map[k]>0)
{
Map[k]--;
}
else if(Map[0]==0)break;
k++;
time++;
}
sort(Map,Map+35,cmp);
}
printf("%d
",time);
}
}
2、核心思路还是上面的思路，但是上面每次都保持数组从大到小的性质可以用优先队列来实现。只是可能要借助临时的数组temp[]来存储从优先队列中pop出的数据。
3、也是大部分AC代码采用的思路。其实不管命令有多少，n等于几，这些命令总是要做完的，所花的时间一定是>=x的。所以只需要看需要填充多少思考人生时间。
上图：
https://coding.net/s/2791e979-c082-43b9-9b28-e43496fe9c76
//用画图画的，专治强迫症
深蓝色的就是用命令填充的，浅蓝色即为“思考人生”时间。
显然总的时间=任务数+思考时间
当只有第一排的1而后面全是浅蓝色时，是需要空闲时间最多的情况，max_num=n*(最多的命令数-1)，因为最后一轮后面是不填充的，所以-1；
我们要做的就是从这个最大值里逐列减去已经有命令的格子。
核心代码如下，可以看图体会：
int Map[35];
for(int i=0; i<35; i++)Map[i]=0;
for(int i = 0; i<tasks.size(); i++)
{
Map[tasks[i]]++;
}
sort(Map,Map+35,cmp);
int max = Map[0]-1;
int slot = max*n;
for(int i = 1;i<31;i++)
{
slot -= min(Map[i],max);
}
int ans;
if(slot>0)ans = slot+tasks.size();
else ans = tasks.size();