社区讨论

只能过一个点的看过了,我来告诉你原因

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 条回复,欢迎继续交流。

正在加载回复...