注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

zstu Single CPU, multi-tasking  

2010-05-14 10:26:07|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

Tuntun is a big fan of Apple Inc. who owns almost all kinds of products the company published. Fascinated by the amazing user experience and fabulous user interface, he spent every nickel of his pocket money on his iMac and iPhone. A few days ago, Apple released their latest iPhone OS 4.0. Tuntun noticed that the most significant new feature of iPhone OS 4.0 is multi-tasking support. He was curious about why the same device with a single core CPU can support multi-tasking under the new operating system. With his clever head, he found out a simple solution. The OS doesn’t have to let the CPU run several tasks exactly at the same time. What the OS should do is just to let the user feel that several tasks are running at the same time. In order to do that, the OS assigns the CPU to the tasks in turn. When the acts of reassigning a CPU from one task to another occur frequently enough, the illusion of parallelism is achieved. Let’s suppose that the OS makes each task run on the CPU for one millisecond every time in turn, and when a task is finished, the OS assigns the CPU to another task immediately. Now if there are 3 tasks which respectively need 1.5, 4.2 and 2.8 millisecond to complete, then the whole process is as follows:

1. At 0th millisecond, task 1 gets the CPU. After running for 1 millisecond, it still needs 0.5 milliseconds to complete.
2. At 1st millisecond, task 2 gets the CPU. After running for 1 millisecond, it still needs 3.2 milliseconds to complete.
3. At 2st millisecond, task 3 gets the CPU. After running for 1 millisecond, it still needs 1.8 milliseconds to complete.
4. At 3rd millisecond, task 1 comes back to CPU again. After 0.5 millisecond of running, it is finished and will never need the CPU.
5. At 3.5 millisecond, task 2 gets the CPU again. After running for 1 millisecond, it still needs 2.2 milliseconds to complete.
6. At 4.5 millisecond, it’s time for task 3 to run. After 1 millisecond, it still needs 0.8 milliseconds to complete.
7. At 5.5 millisecond, it’s time for task 2 to run. After 1 millisecond, it still needs 1.2 milliseconds to complete.
8. At 6.5 millisecond, time for task 3. It needs 0.8 millisecond to complete, so task 3 is finished at 7.3 milliseconds.
9. At 7.3 millisecond, task 2 takes the CPU and keeps running until it is finished.
10. At 8.5 millisecond, all tasks are finished.

Tuntun decided to make a simple iPhone multi-tasking OS himself, but at first, he needs to know the finishing time of every task. Can you help him?

Input

The first line contains only one integer T indicates the number of test cases.
The following 2×T lines represent T test cases. The first line of each test case is a integer N ( 0 < N < = 100 ) which represents the number of tasks, and the second line contains N real numbers indicating the time needed for each task. The time is in milliseconds, greater than 0 and less than 10000000.

Output

For each test case, first output “Case N:”, N is the case No. starting form 1. Then print N lines each representing a task’s finishing time, in the order correspondent to the order of tasks in the input. The results should be rounded to 2 digits after decimal point, and you must keep 2 digits after the decimal point.

Sample Input

2
3
1.5 4.2 2.8
5
3.5 4.2 1.6 3.8 4.4

Sample Output

Case 1:
3.50
8.50
7.30
Case 2:
14.10
17.10
7.60
15.90
17.50
类似模拟题,如果全都用模拟的话就会超时,把数分为整数部分和小数部分,就会豁然开朗。
代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct Node
{
 double a, b, p;
 int num;
};
inline int comp(const Node p1, const Node p2)
{
 if( p1.a > p2.a ) return 1;
 if( p1.a < p2.a ) return 0;
 return p1.num > p2.num;
}
inline int com(const Node p1, const Node p2)
{
 return p1.num < p2.num;
}
int main()
{
 int test, n, i, ii, j;
 while(scanf("%d", &test) != EOF)
 {
  for(ii = 1; ii <= test; ii++)
  {
   Node s[101];
   bool hash[101];
   memset(hash, 1, sizeof(hash));
   scanf("%d", &n);
   for(i = 1; i <= n; i++)
   {
    scanf("%lf", &s[i].a);
    s[i].b = 0;
    s[i].p =  s[i].a - (int)s[i].a;
    s[i].a -= s[i].p;
    if(s[i].p == 0  && s[i].a != 0 ){ s[i].p = 1; s[i].a -= 1.0;}
    s[i].num = i;
   }
   sort(s+1, s+n+1, comp);
   for(i = n; i >= 1; i--)
   {  
    double sum = 0, sum1 = 0;
    for(j = 1; j <= n; j++)
    {
     if(hash[j])
      sum += 1;
     if(hash[j] && s[j].num < s[i].num)
     {
      if(s[j].a >= 1) sum1 += 1;
      else sum1 += s[j].p;
     }
    }
    for(j = 1; j <= n; j++)
    {
     if(hash[j])
     {
      s[j].b += (s[i].a) * sum + s[i].p;
      s[j].a -= (s[i].a);
     }
    }
    s[i].b += sum1;
    hash[i] = 0;
   }
   sort(s+1, s+n+1, com);
   printf("Case %d:\n", ii);
   for(i = 1; i <= n; i++)
    printf("%.2lf\n", s[i].b);
  }
 }
return 0;
}

  评论这张
 
阅读(128)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017