简单模拟，题意描述不清晰，我来仔细描述一下，flashget在下载一些文件，每个文件有一个初始大小，初始速度，最大速度。当一个文件下载结束后，他的速度（占用的带宽）会平均分配给别的任务（各文件的速度增加值相同），假设我们要把速度x分配给a个文件，那么就要给每个文件分配x/a的速度，前提条件是分配后该文件的速度不超过其最大速度。若超过了则不能给他分配这么多，只让它达到其最大速度即可。这样一来我们的下载速度就会有剩余，因为受到最大速度的限制，有些文件并没有被分配到x/a这么多的速度。对于剩余的速度怎么处理呢？就是除去那几个已经到达最大速度的文件，其余文件按照刚才的方法再分配一次剩余速度。模拟即可。这题精度很难控制，我开始试着用先将所有到达最大速度的进程先处理，最后再计算平均值的方法，居然是错的，理论上这种做法比上述做法精度高。
View Code #include#include #include #include #include using namespace std;#define maxn 105struct Elem{ double size, speed, max_speed;} elem[maxn];int n, m;double time_left[maxn];bool finished[maxn];double ans[maxn];double reached[maxn];int task_left;void input(){ scanf("%d", &m); for (int i = 0; i < n; i++) scanf("%lf%lf%lf", &elem[i].size, &elem[i].speed, &elem[i].max_speed);}void cal_time(){ for (int i = 0; i < n; i++) if (!finished[i]) time_left[i] = elem[i].size / elem[i].speed;}void size_reduce(double min_time){ for (int i = 0; i < n; i++) if (!finished[i]) elem[i].size -= min_time * elem[i].speed;}int get_min(){ int ret = 0; while (finished[ret]) ret++; for (int i = ret + 1; i < n; i++) if (!finished[i] && time_left[i] < time_left[ret]) ret = i; return ret;}void distribute(double bandwidth){ double band_left = bandwidth; int num = 0; for (int i = 0; i < n; i++) if (!finished[i] && !reached[i]) num++; if (num == 0) return; double average; while (band_left > 0) { average = band_left / num; bool did = false; for (int i = 0; i < n; i++) { if (finished[i] || reached[i]) continue; did = true; if (elem[i].max_speed - elem[i].speed < average) { band_left -= elem[i].max_speed - elem[i].speed; elem[i].speed = elem[i].max_speed; reached[i] = true; num--; }else { band_left -= average; elem[i].speed += average; } } if (!did) break; }}void work(){ memset(finished, 0, sizeof(finished)); memset(reached, 0, sizeof(reached)); double now_time = 0; task_left = n; while (task_left > 0) { cal_time(); int next_task = get_min(); finished[next_task] = true; task_left--; double bandwidth = elem[next_task].speed; double min_time = time_left[next_task]; size_reduce(min_time); now_time += min_time; ans[next_task] = now_time; distribute(bandwidth); }}int main(){ //freopen("t.txt", "r", stdin); int t = 0; while (scanf("%d", &n), n) { t++; printf("Case %d:\n", t); input(); work(); for (int i = 0; i < n; i++) printf("NO%d:%.3fs\n", i + 1, ans[i]); } return 0;}