[POJ][3836][模拟] P2P File Sharing System

描述：

Peer-to-peer(P2P) 计算技术已经被广泛的应用到因特网数据交换。时下有很多P2P文件分享系统正在流行。

让我们看看一个P2P文件分享系统的简化模型：系统中有很多电脑，它们可以接受数据或将数据发送给别人。为了将问题简化，让我们假设在系统中只有一个大文件需要我们去关注。一些电脑已经拥有完整的文件（我们叫它“服务器”），一些则没有（我们叫它“客户端”）。客户端需要从服务器下载文件。当一个客户端得到了完整的文件，它就变成了一台服务器。

那些电脑不是一直在线。一个在线的客户端会从所有在线的服务器上下载文件。不同的服务器送给客户端不同部分的文件，因此客户端可以快速的下载文件。

现在给出每两台电脑间的传输速度，每台电脑在线及下线的时间以及哪些电脑在一开始就是服务器，请在一段时间内对系统的运行进行分析。

输入：

第一行包含一个整数表示测试数据的数量。

对于每组测试数据：

第1行：它包含两个正整数：n和T （n <= 20, T <= 1000） 意思是系统中有n台编号从1到n的电脑，你的任务是计算出系统开始运行的第T秒钟，每台电脑拥有文件的完整度（百分比）。

第2行：它包含两个正整数：k和S （k <= n, S <= 2^20） 意思是在系统开始运行时有k台服务器以及我们所关注的文件大小为S（KB）。

第3行：它包含K个整数，这是所有服务器的编号。

第4~n+3行：这n行形成一个n*n的矩阵。矩阵的第i行第j个数字表示i号电脑和j号电脑 （i 和 j 从1算起) 间的传输速度（单位 KB/s ，值不超过 2^10）。矩阵是对称的，对角线上的整数没有任何意义。

第n+4~2n+3行：每行包含一台电脑的上线/下线时刻表，格式如下（这些行按升序与电脑编号对应）：

t online_time1 offline_time1 online_time2 offline_time2…online_timet offline_timet

t是一个不超过10的整数，时间全部都是非负的，并且呈升序。在online_timei和offtimei之间的这段时间内，电脑是在线的，并且能从其他电脑上下载数据或传输数据给其他电脑。

第2n+4行：它包含一个正整数m，表示系统中下载行为的数量。

第2n+5~2n+m+4：每行包含两个整数表示一个下载行为，格式如下：

download_timei computer_idi

从时刻download_timei开始，编号为computer_idi的电脑开始下载文件（0 <= download_timei <= T, 1 <= computer_idi <= n）。

这些行按时间非降序给出。保证服务器不会下载文件。保证在时刻download_timei编号为computer_idi的电脑在线（但有可能在发出一个下载命令后立即下线）。

当一个客户端开始下载，它会尝试连接所有的服务器同时从所有在线的服务器上下载数据。客户端的下载速度是所有连接的和。我们假设连接的建立是立即完成的，不花费时间，只有数据的传输会费时。

当一个客户端下线，未完成的下载任务会被保存，并在下次上线时继续。如果一个服务器上线，所有目前正在下载的电脑将会连接它并从中下载数据。更重要的是，当一个客户端变成一个服务器，它将立即开始向客户端传输数据。

注：为了简化问题，用来下载文件的时间应被向上取整（如果文件大小为 6KB 现在速度是 5KB/s，这个下载任务将会花费2秒钟而不是1.2秒钟 — 第一秒下载5KB，下一秒1KB）。

请注意，上述所有时间都以单位秒的形式给出。

输出：

对于每组测试数据，输出应包含n行，每行对应一台电脑。

第i行包含一个百分数，表示第i台电脑从系统开始运行直到T秒钟时所接收的数据的量。格式为‘percentage%’。这个百分数应该被向下取整。

提示：

有两台电脑。文件大小为1024KB，编号为1的电脑在开始时是服务器。当时间到达时刻10秒，编号为2的电脑开始从编号为1的电脑上下载文件直至其在时刻40秒时下线。总共下载了 10KB/s x 30s = 300KB。300/1024 29%。

思路：

按时间流动进行模拟。每过一秒就更新每台客户端的信息。唯一需要注意的是对时刻和时间的区分。

代码：

#include
#include
using namespace std;
struct point
//将每台电脑的信息用结构体封装起来。 
{ 
    bool online[1000];
    //在线时间，若第i秒内处于在线状态，则online[i]==true。 
    int sever_time;
    //该电脑成为服务器的时间。 
    int download_time;
    //开始下载的时刻。 
    int size;
    //拥有数据的大小。 
}computer[20];
//电脑编号从0开始。 
int n,T,k,S,speed[20][20];
//speed[i][j]表示电脑i与电脑j之间的传输速度。 
void input()
//输入 
{
    scanf("%d%d%d%d",&n,&T,&k,&S);
    for(int i=0;i0;t--)
        {
            int online_time,offline_time;
            scanf("%d%d",&online_time,&offline_time);
            for(int j=online_time;j0;m--)
    {
        int download_time,computer_id;
        scanf("%d%d",&download_time,&computer_id);
        computer[computer_id-1].download_time=download_time;
    }
}
void init()
//初始化 
{
    for(int i=0;i<20;i++)
    {
        for(int j=0;j<1000;j++)
            computer[i].online[j]=false;
        computer[i].sever_time=1000;
        computer[i].download_time=1000;
        computer[i].size=0;
    }
}
void solved()
{
    for(int time=0;time=computer[i].download_time&& computer[i].online[time])
            //若该电脑为客户端且已经开始下载并在线。 
                for(int j=0;j=computer[j].sever_time&&computer[j].online[time])
                    //若该电脑为服务器并在线。 
                    {
                        computer[i].size+=speed[i][j];
                        if(computer[i].size>=S)
                        //若该客户端得到了完整的文件。 
                            computer[i].sever_time=time+1;
                            //规定其从下一秒开始成为服务器。 
                    }
}
void output()
//输出 
{
    for(int i=0;i=S?100:computer[i].size*100/S);
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        init();
        input();
        solved();
        output();
    }
}