这题直接sort会tle可以学一学优先队列priority_queue(堆），有可以直接用的stl
by AC_Fox @ 2023-12-15 23:24:34
@[Vanxia1266](/user/956316)
```cpp
#include<bits/stdc++.h>
#define N 10005
int n,a[N],phy=0;
int df(int x) //选择排序
{
int p = x;
for(int i=x+1; i<n; i++)
{
if(a[i]<a[p]) p=i;
}
if(p!=x) {
int t=a[p];
a[p]=a[x];
a[x]=t;
}
return a[x];
}
int main(void)
{
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%d",&a[i]);
for(int i=0; i<n-1; i++)
{
phy+=df(i) + df(i+1);
a[i+1]+=a[i];
}
printf("%d",phy);
}
```
by liqihao2009 @ 2023-12-22 20:59:54
和我原来的想法一样的，其实改法就是优化时间复杂度，while内部的sort做了大量重复动作，导致TLE
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
long long int fruit[10001];
int main()
{
long long int num;
cin >> num;
for (int i = 0; i < num; i++)
cin >> fruit[i];
//int n = sizeof(fruit) / sizeof(fruit[0]);
sort(fruit, fruit + num);
long long int count = 0;
while (fruit[1] != 1e9) {
count += fruit[0] + fruit[1];
fruit[0] += fruit[1];
//fruit[1] = 1e9;
//sort(fruit, fruit + num);
for (int i = 1; i < num - 1; i++)
fruit[i] = fruit[i + 1];
fruit[num - 1] = 1e9;
for (int j = 0; j < num - 1; j++) {
if (fruit[j] > fruit[j + 1]) {
swap(fruit[j], fruit[j + 1]);
}
else {
break;
}
}
}
cout << count;
}
```
by zkystudent2027 @ 2023-12-27 19:14:43
```
#include<iostream>
using namespace std;
int heap[100005],n;
void up(int x) {
while(x>1) {
if(heap[x/2]>heap[x]) {
swap(heap[x/2],heap[x]);
x/=2;
} else
return;
}
}
void down(int x) {
while(x*2<=n) {
int t=x*2;
if(x*2+1<=n&&heap[x*2+1]<heap[x*2])
t++;
if(heap[t]<heap[x]) {
swap(heap[x],heap[t]);
x=t;
} else
break;
}
}
int main() {
int sum=0;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>heap[i];
up(i);
}
int n1=n;
for(int i=1; i<=n1-1; i++) {
int node=heap[1];
heap[1]=heap[n];
n--;
down(1);
node+=heap[1];
heap[1]=heap[n];
n--;
down(1);
sum+=node;
n++;
heap[n]=node;
}
up(n);
cout<<sum;
return 0;
}
```
建议使用堆，sort会超时
by rcbjdws @ 2024-02-03 11:36:26