这是我的老师chatgpt给出的新的解法,但是不能通过样例
by METEOIRITE @ 2023-01-25 20:47:21
@[METEOIRITE](/user/772749) 6
by Martlet @ 2023-01-25 20:56:29
@[METEOIRITE](/user/772749) 这道题拿优先队列做
by Martlet @ 2023-01-25 20:56:58
```
#include<bits/stdc++.h>
using namespace std;
int q;
int cmp(int x,int y)
{
return x<y;
}
int head=1,tail;
int sum;
int a[1110000];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
tail=n;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n-1;i++)
{
q=a[i]+a[i+1];
int j;
for(j=i+1;j<=n-1;j++)
{
a[j]=a[j+1];
if(a[j]>q){a[j]=q;break;
}
}
if(j==n)a[n]=q;
sum+=q;
}
cout<<sum;
return 0;
}
```
@[METEOIRITE](/user/772749)
或者排序之后贪心
by Martlet @ 2023-01-25 20:57:53
我这边chatGPT给的是一个暴力生草的 $O(n^2 \log n)$的排序做法 ~~还说是 n log n 的~~
by qwq_volcano @ 2023-01-25 21:49:36
优先队列是一种数据结构,可以帮助我们实现 P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair 的问题。
具体实现方法是:
创建一个空的优先队列,用于存储每一堆果子的数量。
将每一堆果子的数量插入优先队列。
重复以下步骤直到剩下一堆果子为止: a. 从优先队列中取出最小的两堆果子。 b. 将两堆果子合并为一堆。 c. 将新堆果子插入优先队列。
记录合并果子的次数,并输出。
这种实现方法的时间复杂度是 O(n log n)。
by qwq_volcano @ 2023-01-25 21:58:05