阿里笔试0325第二题
我的思路是用贪心,先是正常数组然后每次sort超时了,然后折腾二十分钟换成优先队列,时间复杂度降低了很多,又给我超时了😅这个题目要求的时间复杂度到底多低?大家有没有正确的解题思路?我想不出来了。
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; #define IN_LEN 5 // 输入五个数 #define INSERT_LEN IN_LEN - 1 // 插入和删除优先队列次数 int main() { int n; cin >> n; vector<vector<long long>> con; for (int i = 0; i < n; i ++) { priority_queue<int> pq; int m; for (int j = 0; j < IN_LEN; j ++) { cin >> m; pq.push(m); } int cnt = -1, flag = 1; while (flag == 1) { int a, b, c, d; for (int j = 0; j < INSERT_LEN; j ++) { int tmp = pq.top(); if (j == 0) a = tmp; if (j == 1) b = tmp; if (j == 2) c = tmp; if (j == 3) d = tmp; pq.pop(); if (tmp - 1 < 0) { flag = 0; break; } } pq.push(a - 1); pq.push(b - 1); pq.push(c - 1); pq.push(d - 1); cnt ++; } printf("%d\n", cnt); } return 0; }