题目
VK 新闻推荐系统每天为每个用户选择 n 个不相交类别之一的有趣出版物。每个出版物都属于一个类别。对于每个类别，我批处理算法选择 ai 出版物。
最新的 A/B 测试表明，如果每个类别在每日推荐中的出版物数量不同，则用户阅读推荐出版物的积极性更高。目标算法可以在 ti 秒内找到第 i 个类别的单个有趣出版物。
将出版物添加到批处理算法执行结果所需的最短总时间是多少，因此所有类别都有不同的出版物数量？您无法删除批处理算法推荐的出版物。
输入
输入的第一行由单个整数 n 组成——新闻类别的数量（1≤n≤200000）。
第二行输入由 n 个整数组成 ai——批处理算法选择的第 i 个类别的出版物数量（1≤ai≤109）。
第三行输入由 n 个整数 ti 组成——目标算法找到一个类别 i 的新出版物所需的时间（1≤ti≤105）。
输出
打印一个整数——目标算法消除具有相同大小的类别所需的最短时间。
题解思路
只能类别加不能减，肯定是从类别小的往大的处理，先让小的固定而不增加，排序，这是第一步贪心。
对于相同类别的数，我们肯定是让时间最大的放在原地。
取最值考虑优先队列，我们讲相同类别的放入队列，拿出一个最大值放在原地，其他的只能让类别自增1，花费他们的时间之和。
我们保证队列中只有相同类别的元素。
当空队的时候，说明之前的元素已经都找到了合适的类别，所以取出之后的元素来当此时的类别，再处理相同的情况。
没空的时候就给它安排位置，以及放入新的相同类别的元素。
还有用并查集做这题的，参考代码。
AC代码
优先队列
#include <bits/stdc++.h>
#define PII pair<int,int>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 200100;
int n ;
PII a[N] ;
void solve()
{
cin >> n ;
for (int i = 1 ; i <= n ; i++ )
{
int t1;
cin >> t1 ;
a[i].first = t1 ;
}
for (int i = 1 ; i <= n ; i++ )
{
int t1;
cin >> t1 ;
a[i].second = t1 ;
}
sort(a+1,a+1+n) ;
priority_queue <int> q ;
int i = 1 ;
int last = 0 ;
long long ans = 0 , res = 0 ;
while ( !q.empty() || i <= n )
{
last++;
if ( !q.size() )
last = a[i].first ;
while ( last == a[i].first && i <= n )
{
res += a[i].second ;
q.push(a[i].second) ;
i++;
}
res -= q.top() ;
q.pop() ;
ans += res ;
}
cout << ans << "\n" ;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve() ;
return 0 ;
}
并查集写法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn=2e5+10;
int n;
map<int,int>fa;
struct node
{
ll num;
int t;
}a[maxn];
bool cmp(node a,node b)
{
return a.t==b.t?a.num<b.num:a.t>b.t;
}
int findf(int x)
{
return fa[x]==0?x:fa[x]=findf(fa[x]);
}
void mix(int x,int y)
{
int xx=findf(x);
int yy=findf(y);
if(xx!=yy)
fa[xx]=yy;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].num;
for(int i=1;i<=n;i++)
cin>>a[i].t;
sort(a+1,a+1+n,cmp);
ll ans=0;
for(int i=1;i<=n;i++)
{
int res=findf(a[i].num);
if(res!=a[i].num)
ans+=1ll*(res-a[i].num)*a[i].t;
mix(res,res+1);
}
cout<<ans<<endl;
return;
}
int main()
{
solve();
return 0;
}
|