VK news recommendation system daily selects interesting publications of one of n disjoint categories for each user. Each publication belongs to exactly one category. For each category i batch algorithm selects ai publications.
The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of i-th category within ti seconds.
What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can’t remove publications recommended by the batch algorithm.
Input
The first line of input consists of single integer n — the number of news categories (1≤n≤200000).
The second line of input consists of n integers ai — the number of publications of i-th category selected by the batch algorithm (1≤ai≤109).
The third line of input consists of n integers ti — time it takes for targeted algorithm to find one new publication of category i (1≤ti≤105).
Output
Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.
Examples
inputCopy
5
3 7 9 7 8
5 2 5 7 5
outputCopy
6
inputCopy
5
1 2 3 4 5
1 1 1 1 1
outputCopy
0
Note
In the first example, it is possible to find three publications of the second type, which will take 6 seconds.
In the second example, all news categories contain a different number of publications.
优先队列，每次都让某一位上的全职最小的加1，2，3然后处理。
#include <bits/stdc++.h>
using namespace std;
int n, t, a[3000000];
struct node
{
int first, second;
bool operator<(const node &b) const
{
if (first == b.first)
return second < b.second;
else
return first > b.first;
}
};
priority_queue<node> ms;
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
for (int i = 0; i < n; ++i)
{
int b;
cin >> b;
ms.push(node{a[i], b});
}
long long cnt = 0;
while (ms.size())
{
auto po = ms.top();
ms.pop();
//cout << po.first << " " << po.second << endl;
//cout << 1 << endl;
if (ms.empty())
break;
int f=1;
while (po.first == ms.top().first && ms.size())
{
auto pi = ms.top();
//cout<<pi.first + 1<<" "<<pi.second<<endl;
ms.pop();
ms.push(node{pi.first + f, pi.second});
cnt += pi.second;
f++;
// cout << cnt << endl;
// cout<<ms.top().first<<endl;
// cout << ms.size() << endl;
}
}
cout << cnt << endl;
}
上分代码的思路确实有问题，时间复杂度太高。思路差不多，都是先处理权值大的，让权值小移动。
#include <bits/stdc++.h>
using namespace std;
int n, t;
struct node
{
int data;
long long cost;
bool operator<(const node &b) const
{
if (cost == b.cost)
return data < b.data;
else
return cost > b.cost;
}
} a[3000000];
map<int, int> fa;
int find(int a)
{
if (fa[a] == 0)
return a;
else
return fa[a] = find(fa[a]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x != y)
fa[x] = y;
}
int main()
{
cin >> n;
fa.clear();
for (int i = 0; i < n; ++i)
scanf("%d", &a[i].data);
for (int i = 0; i < n; ++i)
scanf("%lld", &a[i].cost);
sort(a, a + n);
long long ans = 0;
for (int i = 0; i < n; i++)
{
int x=find(a[i].data) ;
ans += a[i].cost * (x- a[i].data);
unite(x,x+1);
}
cout << ans << endl;
}