Link

http://codeforces.com/problemset/problem/589/K

Problem

Vasya wants to create a computing system to process arbitrary tasks. As a part of the system he needs an algorithm which will choose an order of task execution.

He came up with the following algorithm:

  • There is a single execution queue. For task to be completed, it needs to be added to the queue.
  • For each task two values are known: li and ti — the number of seconds that it takes to complete the task and the moment of time when this task is added to the execution queue.
  • If at some moment of time T the algorithm has to select a task for execution, it picks the one with the minimum value of li - (T - ti)2. In case of a tie, algorithm picks a task with the lowest index. Then for the following li seconds the algorithm will wait for the task to be completed.

In order to test the algorithm Vasya wants you to simulate it.

You are given n tasks. For each task, you know the number of seconds li that it takes to complete the task and the moment of time ti when this task is added to the execution queue.

For each task find out the moment of time when it will be completed.

Mean

有一个单任务执行队列和N个任务,每个任务在第ti秒加入队列,需要执行li秒。每个任务执行后从队列中选择li - (T - ti)最小的任务执行,当前时间为T。输出每个任务执行完毕的时间。

Analysis

其实这就是一个水题…个人赛场上都不做这道题,由于自己的失误也没有AC,当时就是落了一个排序条件,加上之后顺利AC。

首先从队列中查找当前优先级最高的任务,我们只需要对t排序。由于l的上限为100000,所以当t的差值很大直到t^2超过100000时,l对优先级的贡献便失去作用。这样我们只需要扫描前333个t最小的任务即可。

当t相同时,优先选择l最小的任务,这样可以将t相同的维护在一个优先队列,方便查询和删除。

PS…这道题没出真的挺可惜的,以后碰到没人做的题,自己觉得能出,还是要大胆做一下改一下调一下bug…说不定能AC…

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct Node {
    int len, add, id;
    Node(int len = 0, int add = 0, int id = 0):
            len(len), add(add), id(id) {}
    bool operator < (const Node &rhs) const {
        return len == rhs.len ? id > rhs.id : len > rhs.len;
    }
};
const int maxn = 102400, inf = 0x3f3f3f3f;
int N;
Node v[maxn];
map<int, priority_queue<Node>> qu;
ll res[maxn];

inline ll sqr(ll x) {
    return x * x;
}

int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) {
        scanf("%d%d", &v[i].len, &v[i].add);
        v[i].id = i;
    }
    sort(v + 1, v + N + 1, [](const Node &a, const Node &b) { return a.add < b.add; });
    ll T = 0;
    int pos = 1;
    while(true) {
        if(pos <= N && qu.empty() && T < v[pos].add) {
            T = v[pos].add;
        }
        while(pos <= N && v[pos].add <= T) {
            qu[v[pos].add].push(v[pos]);
            pos += 1;
        }
        if(qu.empty()) break;
        int stadd = qu.begin()->first;
        ll best = 0x3f3f3f3f3f3f3f3f;
        int bestid = qu.begin()->second.top().id;
        int ans = stadd;
        for(auto &i : qu) {
            if(sqr(i.first - stadd) > maxn)
                break;
            ll cur = i.second.top().len - sqr(T - i.first);
            int curid = i.second.top().id;
            if(cur < best || (cur == best && curid < bestid)) {
                best = cur;
                bestid = curid;
                ans = i.first;
            }
        }
        T += qu[ans].top().len;
        res[bestid] = T;
        qu[ans].pop();
        if(qu[ans].empty())
            qu.erase(ans);
    }
    for(int i = 1; i <= N; ++i) {
        printf("%I64d%c", res[i], i==N ? '\n' : ' ');
    }
    return 0;
}

欢迎留言