Codeforces Round 623(Div. 2,based on VK Cup 2019-2020 - Elimination Round,Engine)D. Recommendations
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;
}
最新文章
- Session和Cache的区别
- Spring AOP 开发中遇到问题:Caused by: java.lang.IllegalArgumentException: warning no match for this type name: com.xxx.collector.service.impl.XxxServiceImpl [Xlint:invalidAbsoluteTypeName]
- linux命令学习(1):grep 命令
- Java泛型数组
- [转]Calling Web Service Functions Asynchronously from a Web Page 异步调用WebServices
- CTEX里的函数、符号及特殊字符
- Sqli-labs less 64
- C++调试 输出数组内容和数组名
- HTML5课程大纲/学习路线
- TTB 基本
- go orcale
- EntityFramework6.X之DataAnnotations
- 优先队列的二叉堆Java实现
- ELK配置
- Python数据结构之单链表
- 转://因触发器限制导致oracle用户登录失败
- RN Animated透明度动画
- msysgit使用方法
- Android——sqlite3 基本命令操作
- D3.js 使用心得
热门文章
- linux系统管理,查看系统资源
- Linux 磁盘管理篇,连接文件
- idea 快捷键 pvsm sout
- django 前后台传递数据
- python3(三十一)metaclass
- python3(二十五) getClassInfo
- Pytest系列(21)- allure的特性,@allure.description()、@allure.title()的详细使用
- Python-气象-大气科学-可视化绘图系列(三)—— 地图上自动标注省会名称(demo调整中)(代码+示例)
- 用python爬取之后发现果然如此,都说知乎的小姐姐漂亮
- stand up meeting 1/8/2016 &; weekend 1/9/2016~1/10/2016 &;&; sprint2扫尾