T3-2:小明的积木
2024-10-02 14:11:54
发布于:天津
第二题
题目大意
题目给出一个长度为的序列a,分为两块部分,为 数量与数值
现在你可以使用当中的去搭建一个积木塔的数字序列。积木塔的数字序列的要求为
我们设定积木塔的序列名称为,则需要
,与才可以连接在一起。
现在你可以使用序列去组件个序列,每个的val可以背使用的次数为count,求解所有的序列b总计最多使用多少数字。
根据贪心原理,我们可以很快得知,如果你想要让一个序列尽可能的长,你就需要将较小的数字放置于上方,较大的放置于下方,尽可能按照这样去排放,才可以让其最长。
- Sort对于a数组按照val的数值进行从小到大排序。
- 使用for循环枚举m个序列b
- 再放一个for循环,寻找组成b的合法元素
struct Node{
int val;
int count;
}a[1000005];
bool cmp(Node a,Node b)
{
return a.val < b.val;
}
int answer = 0 ; // 使用个数
for(int i = 0 ; i < m ; i ++ )
{
int last = 0; // 代表前一个序列的字符
for(int j = 1 ; j <= n ; j ++ )
{
if(a[j].count == 0)continue;
if(last == 0 || a[j].val - last >= k ){
// a[j]连接到徐莲当中
last = a[j].val;
answer ++ ;
a[j].count -- ;
}
}
}
cout << answer << endl;
- 循环遍历m组积木塔 O(m)
- 循环寻找n个数字查看是否可以添加到积木塔当中。 O(n)
我们添加数字到积木塔当中时,是一个个添加进去的,也就是说非常的低效,有没有一种办法,在遍历当前第i个数字的时候,我们就可以知道当前这个数字能放到多少个积木塔当中呢?
假如说,存在一种方法,使得我们在遍历n个数字的时候,每遍历一个数字,就可以将其分配到m个积木塔当中,并且不需要循环来匹配,那么时间复杂度就可以降至O(n)。
我们思考一件事情,积木塔的长度没有限制,也就是说,我们可以任意的往积木塔当中添加符合条件的数字。
假设已经按照从小到大的顺序排列好了数字,那么我们从数字当中拿取拼接到积木塔当中的遍历顺序一定是从左往右。
假如说,当前拿取的数字是a[id].value,对于所有与他差值为k的数字都可以接在后面。那么我们是不是可以认为所有差值为k的数字总数可以直接累加进答案里?
假设a[id].value = 1 ,现在有其他value与count分别为 [2,5][3,6] ,且k=1.
那我们是不是可以直接认为答案answer 可以加 5和6?
不可以,原因为: 以1作为上一个元素的积木塔可能没那么多。
所以可以累加的大小为 min(m,5) 或min(m,6)或min(m,5+6)。
又或者1的数量只有3个,那么只能接3个数字在后, 优先选择较小的。
但是在这里,我们可以发现一个关键性的问题,我们没必要一个个匹配过去,我们完全可以把一个的count个数字直接平铺在某一层当中。然后在到其他的数字当中寻找可以衔接在下一层的其他数字继续平铺。
那么我们在这里设定上一个数字的编号为 id 开始书写。
#include<iostream>
using namespace std;
struct Node{
int value,count;
}a[2000005];
int ans[20000005] ; // 记录使用的数字数量
bool cmp(Node a,Node b){
return a.value < b.value ;
}
long long res ;
int id;
int main()
{
int n,m,k;
cin >> n >> m >> k ;
for(int i = 1 ; i <= n ; i ++ )cin >> a[i].value >> a[i].count;
id = 1;
sort(a+1,a+1+n,cmp);
//排序,设定好上一个数字的下标
for(int i = 1 ; i <= n ; i ++ )
{
// 枚举每一个数字
while(id < i && a[i].value - a[id].value >= k){ // 平铺衔接在后面
// 判断当前枚举的数字是否可以衔接在上一层数字后面,把可以衔接上去的数字丢上去
m += ans[id ++ ]; // 已经被使用的数字放置在ans数组当中,假如上一层被使用了ans[id]个数字,
//那么现在就可以接上对应的数字层数
// 假如当前数字可以完全衔接,那么就丢上去,m储存当前可以衔接的数字总数
}
ans[i] = min(m,a[i].count); // 取当前可以作为剩余积木塔起点的数字
m -= ans[i]; res += ans[i] ; // 去除这些数字作为衔接数字,并且累计使用个数
}
cout << res << endl;
return 0;
}
这里空空如也
有帮助,赞一个