Я попробовал вопрос PS, упомянутый здесь .
Задача.
У вас есть программа, которая распараллеливается и использует n независимые потоков для обработки данного списка m заданий. Потоки принимают задания в том порядке, в котором они указаны во входных данных. Если есть свободный поток, он немедленно берет следующее задание из списка.
Если поток начал обработку задания, он не прерывается и не останавливается, пока не завершит обработку задания.
Если несколько потоков одновременно пытаются взять задания из списка, поток с меньшим индексом берет задание. Для каждого задания вы точно знаете, сколько времени потребуется любому потоку, чтобы обработать это задание, и это время одинаково для всех потоков.
Вам необходимо определить для каждого задания, какой поток будет его обрабатывать и когда будет он начинает обработку.
Формат ввода.
Первая строка входных данных содержит целые числа n и m. Вторая строка содержит m целые числа t_i - время в секундах, которое требуется любому потоку для обработки i-го задания. Время указано в том же порядке, что и в списке, из которого потоки берут задания. Потоки индексируются, начиная с 0.
Ограничения.
1 ≤ n ≤ 10 ^ 5; 1 ≤ m ≤ 10 ^ 5; 0 ≤ ti ≤ 10 ^ 9.
Формат вывода.
Вывести ровно m строк. i-я строка (используется индекс с отсчетом от 0) должна содержать два целых числа, разделенных пробелами: отсчитываемый от 0 индекс потока, который будет обрабатывать i-е задание, и время в секундах, когда он начнет обработку этого задания.
Моя реализация отлично работает для базовых c тестовых случаев. Однако в некоторых тестах это не удастся. Какую ошибку я здесь не увидел?
Пример ввода
2 5
1 2 3 4 5
Выход
0 0
1 0
0 1
1 2
0 4
Вот мой код.
#include <iostream>
#include <queue>
using std::cin;
using std::cout;
using std::endl;
using std::ios_base;
using std::pair;
using std::priority_queue;
using std::queue;
using std::vector;
#define For(i,a,n) for (int i = a; i < n; i++)
typedef pair<int,int> PII;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m,t,val;
PII p;
priority_queue<PII> pq;
queue<int> q;
// inputs >> number of treads, jobs
cin >> n >> m;
// time to process each job
For(i,0,m){
cin >> t;
q.push(t);
}
// priority_queue
// contains pair {-time, -tread}
For(i,0,n) pq.push({0, -i});
// untill finish all jobs
while(!q.empty()){
// get the smallest time tread
p = pq.top();
pq.pop();
// print the output << tread no , start time
cout << -p.second << " " << -p.first << endl;
// get the next value in the queue
val = q.front();
q.pop();
// push the given tread with new end time
pq.push({ -val + p.first, p.second });
}
return 0;
}
Следующий код python3 отлично подходит для решения этой проблемы. Однако я не могу найти никакой разницы в функциональности в обоих из них. В чем проблема с реализацией c ++.
import sys
import heapq
def read():
return [int(i) for i in sys.stdin.readline().strip().split()]
n, m = read()
arr = read()
q = []
for i in range(n):
heapq.heappush(q, (0, i))
for i in range(m):
x, y = heapq.heappop(q)
print(y, x)
heapq.heappush(q, (x+arr[i], y))
Спасибо за каждый ответ.