题目描述 现在你有N种书,编号从1到N。现在已经知道每种书有a[i]本(1<=i<=N),每本书售价v[i]元。你想买再买一些书使得你拥有的所有书的本数各不相同。请问实现这个想法的最小花费是多少? 样例输入 复制 3 1 2 2 3 1 1 样例输出 复制 1 提示 1<=N<=200000 ; 1<=a[i]<=10^9 ; 1<=v[i]<=10^5c++
时间: 2024-04-15 20:25:10 浏览: 11
这个问题可以用贪心算法解决。首先,我们将书的本数按照从小到大的顺序排序,然后从第二本书开始,如果当前的书的本数和前一本书的本数相同,我们就将当前书的本数加1,直到它和前一本书的本数不同为止。这样做的目的是保证每种书的本数各不相同。
在进行上述操作的过程中,我们计算每次增加书本数时所需花费的最小值,并累加得到总花费。最后输出总花费即可。
以下是一个示例的C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> a(N), v(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
for (int i = 0; i < N; i++) {
cin >> v[i];
}
sort(a.begin(), a.end());
long long cost = 0;
int prev_count = a[0];
for (int i = 1; i < N; i++) {
if (a[i] <= prev_count) {
cost += v[i];
prev_count = max(prev_count + 1, a[i]);
} else {
prev_count = a[i];
}
}
cout << cost << endl;
return 0;
}
```
注意,由于题目中给出的限制条件较大,为了避免整数溢出,我们使用了 `long long` 类型来保存花费。