HDU 3269 P2P File Sharing System 【模拟,时间轴做法】

原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3269

Source2009 Asia Ningbo Regional Contest Hosted by NIT  J 稍微有点麻烦的模拟

题目大意:

                   模拟BT下载的文件传输方式。

                   直接解释数据:

tcase

n(n <= 20)台电脑,T(T <= 1000):模拟过程的总时间(这才是进行模拟的关键轴)。(单位:second

k表示有k台电脑初始时作为服务器直接提供文件下载,S:下载文件的大小(在模拟过程中只有一个文件可供下载)。(单位:kb

此行有k个数:表示作为服务器的k台电脑的编号id(或者说标记名称)。

一个n*n的对阵矩阵,matrix[i][j]的值表示编号为i和编号为j的电脑互相之间下载上传速度(带宽不被分享,即恒定),主对角线均为0,因为自身无传输速度。

接下来n行:第i行对应编号为i的电脑,每行第一个数为t,表示第i台电脑有t段在线时间,接下来2t个数,分别表示第t段时间的开始时间点和结束时间点(即第i台电脑的上线时间和下线时间,时间段为左闭右开,即下线时间点不提供下载上传服务)。

m表示有m次下载操作。(因为每台电脑的下载操作只需执行一次,便会一直在时间轴界限(<=T)内一直执行,又因为没有终止下载操作,所以对于每台电脑来说,最多只会有一个执行操作,所以虽然m未给数据范围,但是显然,m<=n

m行:每行第一个数表示下载开始时间点t(i),第二个数表示开始下载的电脑c(i)

(保证初始为服务器的电脑不会被要求执行下载的命令)

(虽然一台电脑被执行了下载命令,可是若它不在线,也不能下载,只是出于挂起状态,等待上线)

(当某台电脑的文件下载完成度达到100%以后,自动变为服务器,开始上传,不再执行下载操作)

(客户端电脑会从所有服务器同时进行下载)

(因为下载时间是上取整,所以按时间轴模拟的话,最后文件完成度要进行下取整,互逆操作啊~

#include <iostream>

#include 
<cstdio>

#include 
<cmath>

using namespace std;

int n,T,k,S;//机数,时间轴长度,初始服务器数量,文件大小

bool ser[25];//标记某台电脑是否为服务器

int mat[25][25];//传输速度矩阵

int t;//在线时间段数

bool TIME[25][1005];//利用离散化思想通过标记数组记录每台电脑在线时间点

int on,off;

int m;//操作数

bool click[25];//当有下载命令下达时,某台电脑才会变为客户端,该标记数组用以确定某台电脑是否被激活变成进行下载的客户端

struct command//该结构体用以扫描时间标记数组以确定某特定时间点哪一台电脑被激活

{

    
int t,c;//表示t时间点第c台电脑被激活

}co[
30];

bool com[1005];//所谓时间标记数组,用以记录时间轴上哪一点有激活操作发生

int cont[25];//某台电脑上“关键文件”的剩余需下载量(初始为S,服务器为0)

void solve()

{

    scanf(
"%d%d",&n,&T);

    scanf(
"%d%d",&k,&S);

    
for(int i = 1;i <= n;i++)//初始化时间轴

        
for(int j = 0;j <= T;j++)

            TIME[i][j] 
= 0;

    
for(int i = 0;i <= T;i++)//初始化时间标记数组

        com[i] 
= 0;//command seq init

    
for(int i = 1;i <= n;i++)//各种init

    {

        ser[i] 
= 0;

        cont[i] 
= S;

        click[i] 
= 0;

        co[i].t 
= -1;//时间轴从0开始,将命令操作初始存在时间改为-1以防WA

    }

    
for(int i = 1;i <= k;i++)//which is server

    {

        
int a;

        scanf(
"%d",&a);//确定初始服务器

        ser[a] 
= 1;

        cont[a] 
= 0;//规范化服务器的文件剩余量

    }

    
for(int i = 1;i <= n;i++)//trans velocity to each other

        
for(int j = 1;j <= n;j++)

            scanf(
"%d",&mat[i][j]);//读入矩阵

    
for(int i = 1;i <= n;i++)//读入第i台电脑的在线时间段

    {

        scanf(
"%d",&t);//t segments

        
for(int j = 1;j <= t;j++)

        {

            
int a,b;

            scanf(
"%d%d",&a,&b);

            
for(int z = a;z <= b - 1;z++)

                TIME[i][z] 
= 1;//离散化思想储存第i台的在线时间点

        }

    }

    scanf(
"%d",&m);//m operation.

    
for(int i = 1;i <= m;i++)

    {

        scanf(
"%d%d",&co[i].t,&co[i].c);//第t时间第c台电脑被激活

        com[co[i].t] 
= 1;

    }

    
for(int i = 0;i <= T;i++)//时间轴上扫描

    {

        
//key..judge

        
if(com[i] == 1)//如果该时间点有激活操作发生

        {

            
for(int j = 1;j <= n;j++)//搜索对应激活操作的是哪台电脑

                
if(co[j].t == i)

                    click[co[j].c] 
= 1;//标记激活

        }

        
//handle

        
for(int j = 1;j <= n;j++)//第j台电脑

        {

            
if(click[j] == 1 && TIME[j][i] == 1 && ser[j] == 0)//已激活,在线,非服务器

            {

                
for(int z = 1;z <= n;z++)//扫描所有电脑和第j台电脑的关系

                {

                    
if(ser[z] == 1)//如果z是服务器

                    {

                        
if(TIME[z][i] == 1)//z在线,i时刻

                        {

                            cont[j] 
-= mat[j][z];//那么就在i时刻,z传给j,mat[j][z]大小的文件块

                        }

                    }

                }

            }

        }

        
for(int j = 1;j <= n;j++)//每秒过后扫描是否有新的电脑变成服务器提供下载,关键!

        {

            
if(cont[j] <= 0)

            {

                cont[j] 
= 0;

                ser[j] 
= 1;

            }

        }

    }

    
for(int i = 1;i <= n;i++)

    {

        
double rate = (double)(S - cont[i]) * 100 / S;//输出完成度,用下取整(对应题目中上取整)

        printf(
"%.0lf",floor(rate));

        cout 
<< '%' << endl;

    }

}   

int main()

{

    
int ca;

    
while(cin >> ca){

        
for(int i = 0;i < ca;i++)

        solve();}

}

//欢迎大牛拍我

posted on 2011-07-05 13:16 BUPT-[aswmtjdsj] @ Penalty 阅读(334) 评论(0)  编辑 收藏 引用 所属分类: HDU Solution Report 模拟


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜