社区讨论
只能过一个点的看过了,我来告诉你原因
P1090[NOIP 2004 提高组] 合并果子参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6h7kmf
- 此快照首次捕获于
- 2025/11/20 04:49 4 个月前
- 此快照最后确认于
- 2025/11/20 04:49 4 个月前
首先上代码,不会markdown,格式不好见谅
使用二叉堆存储每一推的大小,每次合并最小的两个堆,合并到只剩下一个元素时停止。
我的代码还有很多可以优化的地方,不过勉强能理解
CPP
#include <iostream>
#include <algorithm>
#define swap(a,b) std::swap(a,b)
int heap[10010];
int n;
void down(int i){
int t=0,flag=0;
while(i*2<n && !flag){
if(heap[i]>heap[i*2]){
t=i*2;
}
else{
t=i;
}
if(i*2+1<n){
if(heap[t]>heap[i*2+1]){
t=i*2+1;
}
}
if(i!=t){
swap(heap[t],heap[i]);
i=t;
}else{
flag=1;
}
}
return ;
}
void buildheap(){
for(int i=n/2;i>=0;i--)
down(i);
return ;
}
int delmin(){
int ret=heap[0];
swap(heap[0],heap[n-1]);
heap[n-1]=0;n--;
down(0);
return ret;
}
void insert(int x){
heap[n]=x;
down(n);
int i=n;
while(i>0){
if(heap[i]<heap[i/2]){
swap(heap[i],heap[i/2]);
i/=2;
}else{
break;
}
}
n++;
}
int main(int argc, char const *argv[]) {
std::cin >> n;
for(int i=0;i<n;i++)
std::cin >> heap[i];
buildheap();
int work=0;
int a,b;
while(n>0){
if(n==1){
break;
}
a=delmin();b=delmin();
work+=(a+b);
insert(a+b);
}
std::cout << work << '\n';
return 0;
}
然后是过一个点的原因,你多半是直接用了线性结构存储。
排序,每次将最前面两个元素合并,插入原来的线性结构。
这种方法的问题在于,两个元素合并后可能存在两个小于这个合并出来的堆,说白了就是直接再用这个合并出来的堆和其他元素合并,不能保证合并两个最小的,所以错误。
第一个数据节点可能由于数据问题,
3
1 2 9
这个数据
前两个合并得到
work = 3
n=2
3 9
此时合并 3,9是最优
然而很容易找到反例
5
1 2 2 3 3
work = 0
n = 5
合并
work = 3
3 2 3 3
合并
work = 5
5 3 3
###这里出现问题了,应该合并最小的 3 ,3 而不是前面的5,3
正确的做法是要保证每次取出的两个元素最小,这个容易想到使用小根二叉堆结构来存储数据,懒得自己写的话用
queue中的std::priority_queue,但是这个默认比较器是std::less()效果是达到大根堆,所以你需要制定比较器为
std::greater()怎么制定比较器?那当然是自己看文档了。
好了,写了这么长,应该解决您过一个点的问题了,如果还是不行的话,请参考其他dalao的AC程序,自己开split diff比较一下,gdb调一下,看看哪里有问题。还在CE,TLE的同志可以回去补CPP课程了,coursera上有pku开的专项课程自己看看就行了。
回复
共 4 条回复,欢迎继续交流。
正在加载回复...