QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#533895 | #7523. Partially Free Meal | rikka_lyly | TL | 0ms | 3624kb | C++20 | 3.3kb | 2024-08-26 16:16:13 | 2024-08-26 16:16:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
struct KBIG
{
int k = 0;
ll sum = 0;
priority_queue<int, vector<int>, greater<int>> pq1;
priority_queue<int> pq2;
KBIG()
{
k = 0;
sum = 0;
}
void insert(int x)
{
if(pq1.size() < k)
{
pq1.push(x);
sum += x;
return;
}
pq1.push(x);
sum += x;
pq2.push(pq1.top());
sum -= pq1.top();
pq1.pop();
}
void resetk(int kk)//这个k必须比之前的k大
{
k = kk;
while (!pq2.empty() && pq1.size() < k)
{
pq1.push(pq2.top());
sum += pq2.top();
pq2.pop();
return;
}
}
ll getsum()const
{
return pq1.size() == k ? sum : -1;
}
};
void solve()
{
int n;
cin >> n;
vector<int> a0(n + 2), b0(n + 2);
for (int i = 1; i <= n; i++)
{
cin >> a0[i] >> b0[i];
}
auto cmp = [&](int x, int y) -> bool
{
return b0[x] < b0[y];
};
vector<int> temp(n + 2);
for (int i = 1; i <= n; i++)
{
temp[i] = i;
}
sort(temp.begin() + 1, temp.end() - 1, cmp);
vector<int> a(n + 2), b(n + 2);
for (int i = 1; i <= n; i++)
{
a[i] = a0[temp[i]], b[i] = b0[temp[i]];
}
vector<int> f(n + 2, -1);
vector<ll> ans(n + 2, INF);
f[0] = 1, f[n] = n;
if(1)//先把ans[n]求出来免得夜长梦多
{
ll sum = 0;
for (int i = 1; i <= n; i++)
{
sum += a[i];
}
ans[n] = sum + b[n];
}
while (1)
{
//找一下这一层需要处理那些f,以及其前后已经算出来f的数
vector<pair<int, pair<int, int>>> vt;
for (int i = 1, last = 0; i <= n; i++)
{
if(f[i] == -1)
continue;
if(last + 1 == i)
{
last = i;
continue;
}
vt.push_back({(last + i) >> 1, {last, i}});
last = i;
}
if(vt.empty())
break;
int p = 1;
KBIG kb;
for (auto &[cur, rng] : vt)
{
// cerr << cur << " ";
kb.resetk(cur - 1);
int l = f[rng.first], r = f[rng.second];
{
ll tans = kb.getsum();
if(tans != -1 && tans + a[p] + b[p] < ans[cur])
{
ans[cur] = tans + a[p] + b[p];
f[cur] = p;
}
}
while (p < r)
{
kb.insert(a[p++]);
ll tans = kb.getsum();
if(tans != -1 && tans + a[p] + b[p] < ans[cur])
{
ans[cur] = tans + a[p] + b[p];
f[cur] = p;
}
}
}
// cerr << endl;
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
while (t--)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 2 5 4 3 3 7
output:
7 11 16
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
input:
200000 466436993 804989151 660995237 756645598 432103296 703610564 6889895 53276988 873617076 822481192 532911431 126844295 623111499 456772252 937464699 762157133 708503076 786039753 78556972 5436013 582960979 398984169 786333369 325119902 930705057 615928139 924915828 506145001 164984329 208212435...