535 条题解
-
0
pipixue LV 7 @ 2018-06-11 10:40:20
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue <int,vector<int>,greater<int> >q;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
q.push(a);
}
int ans=0;
while(1){
int a=q.top();
q.pop();
if(q.empty())break;
else{
int b=q.top();
q.pop();
ans+=a+b;
q.push(a+b);
}
}
printf("%d",ans);
return 0;
} -
0
简单贪心
主要算法：
每次合并最小值和次小值
然后进行删除
附代码
cpp
#include<iostream>
using namespace std;
const int num = 10005;
int apple[num];
int ans = 0;
int main() {
int n;
cin >> n;
for(int i = 0;i < n;i++)
cin >> apple[i];
while(n > 1) {
int min1 = 0,min2 = 1; // 查找最小值和次小值
if(apple[min1] > apple[min2])
swap(min1,min2);
for(int i = 2;i < n;i++) {
if(apple[i] < apple[min1]) {
min2 = min1;
min1 = i;
}
else if(apple[i] < apple[min2])
min2 = i;
}
// 将最小值那个位置的数据修改为相加后的值
// 另外将次小值那个位置的数据修改为appl[n-1]的值
// 这样在n--时不会丢失数据
if(min1 == n - 1) swap(min1,min2);
int t = apple[min1] + apple[min2];
ans += t;
apple[min1] = t;
apple[min2] = apple[n - 1];
n--;
}
cout << ans;
return 0;
}
-
0
#include<stdio.h>
int main()
{
int n, a[10000];
scanf("%d", &n);
int i, min1, min2;
int sum = 0;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
min1 = 0, min2 = 1; //其实初始化min1和min2是0或者1都无所谓
int t = n - 1; //注意到这里要复制一个n
while (t--) //是先判断t，再自减，故上一行需要n-1
{
for (i = 0; i < n; i++) //找到最小值和次小值的下标，无论min1和min2值如何，都可以找到最小和次小
{
if (a[i] < a[min1])
{
min2 = min1;
min1 = i;
}
else if (a[i] >= a[min1] && a[i] < a[min2] && i != min1)
min2 = i;
}
sum += a[min1] + a[min2];
a[min2] += a[min1]; //把次小值更新为和
a[min1] = 99999999; //把最小值标记为一个足够大的值
}
printf("%d", sum);
return 0;
} -
0
重新燃起算法热情的小虾米 LV 6 @ 2018-05-23 14:37:28
使用优先队列即可快速解决此题
#include<iostream>
#include<queue>
#include<vector>using namespace std;
struct cmp{
bool operator ()(long &a,long &b) const
{
return a > b;
}};
int main()
{
priority_queue<long,vector<long>,cmp> qp;
int n,i;
long sum = 0,temp;
cin>>n;
for(i = 0;i < n;i++)
{
cin>>temp;
qp.push(temp);
}
while(qp.size() > 1)
{
long t1,t2;
t1 = qp.top();
qp.pop();
t2 = qp.top();
qp.pop();
t1 = t1 + t2;
sum += t1;
qp.push(t1);
}
cout<<sum;
return 0;
} -
0
lk983773710 LV 7 @ 2018-05-12 21:34:41
#include <iostream>
#include <algorithm>
using namespace std;
int gg[20001];
int main(int argc, char** argv)
{
long long tt=0;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>gg[i];
}
for(int j=1;j<n;j++)
{
sort(gg+j,gg+1+n);
tt=tt+gg[j]+gg[j+1];
gg[j+1]=gg[j]+gg[j+1];
}
cout<<tt;
return 0;
} -
0
每次取最小的两个数求和，然后塞回去。
这不明摆着让你用堆去维护吗？我在想数据规模再大点会不会搞死你们这帮每次都要重新排序的XDimport java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { static FileReader fr; static int n; static int[] heap; static int count; public static Scanner getInput() { return new Scanner(System.in); } // public static Scanner getInput() throws IOException { // File f = new File("input.txt"); // fr = new FileReader(f); // Scanner sc = new Scanner(fr); // return sc; // } private static void maintaince() { int index = 1; while (true) { int value = heap[index]; int minValue = value; if (index * 2 + 1 <= count) { int lValue = heap[index*2]; int rValue = heap[index*2+1]; minValue = Math.min(lValue, minValue); minValue = Math.min(rValue, minValue); if (minValue == lValue) { int tmp = heap[index]; heap[index] = heap[index*2]; heap[index*2] = tmp; index = index * 2; }else if (minValue == rValue) { int tmp = heap[index]; heap[index] = heap[index*2 + 1]; heap[index*2 + 1] = tmp; index = index * 2 + 1; }else { break; } }else if (index * 2 == count) { int lValue = heap[index*2]; minValue = Math.min(lValue, minValue); if (minValue == lValue) { int tmp = heap[index]; heap[index] = heap[index*2]; heap[index*2] = tmp; index = index * 2; }else { break; } }else { break; } } } private static void maintaince2() { int index = count; while (index > 1) { int value = heap[index]; int rootValue = heap[index/2]; if (rootValue > value) { int tmp = heap[index]; heap[index] = heap[index/2]; heap[index/2] = tmp; index = index / 2; }else { break; } } } public static void input() throws IOException { Scanner sc = getInput(); n = sc.nextInt(); heap = new int[n+1]; for (int i = 0; i < n; i++) { int value = sc.nextInt(); addValue(value); } if (fr != null) { fr.close(); } } private static int getMin() { int min = heap[1]; heap[1] = heap[count]; count--; maintaince(); return min; } private static void addValue(int value) { count++; heap[count] = value; maintaince2(); } public static int algorithm() { int result = 0; while (count > 1) { int min1 = getMin(); int min2 = getMin(); int neo = min1 + min2; result += neo; addValue(neo); } return result; } public static void output(int result) { System.out.println(result); } public static void main(String args[]) throws IOException { input(); int result = algorithm(); output(result); } } -
0
用set容器自动排序的特点可以实现
#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
multiset<long long>aa;
int main(){
long long n,i,a,b,c,sum=0;
multiset<long long>::iterator it;
cin>>n;
for(i=1;i<=n;i++) {scanf("%lld",&a); aa.insert(a);}
while(aa.size()!=1){
it=aa.begin();
sum+=*it;
b=*it;
aa.erase(it);
it=aa.begin();
c=*it;
sum+=c;
aa.erase(it);
aa.insert(b+c);}
printf("%lld",sum);
return 0;
} -
0
zhaomingyang2017 LV 3 @ 2018-04-07 20:11:59
#include<stdio.h>
long long a,b,c=0;
int main()
{
scanf("%d",&a);
for(int z=1;z<=a;z++)
{
scanf("%d",&b);
c=b+c+c;
}
printf("%d ",c);
return 0;
} -
0
wangjun_92 LV 6 @ 2018-04-04 13:58:05
import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Queue<Integer> fruit = new PriorityQueue<Integer>(); for(int i = 0;i < n;i ++){ fruit.add(scanner.nextInt()); } scanner.close(); int total = 0; while(fruit.size()>1){ int sum = fruit.poll() + fruit.poll(); fruit.add(sum); total += sum; } System.out.println(total); } } -
0
分享下堆的做法
get()是取出小根堆的根节点
put()是在堆中加入一个元素
效率很高状态 耗时 内存占用
#1 Accepted 12ms 364.0 KiB
#2 Accepted 3ms 384.0 KiB
#3 Accepted 4ms 368.0 KiB
#4 Accepted 4ms 384.0 KiB
#5 Accepted 7ms 360.0 KiB
#6 Accepted 8ms 376.0 KiB
#7 Accepted 7ms 364.0 KiB
#8 Accepted 7ms 372.0 KiB
#9 Accepted 4ms 384.0 KiB
#10 Accepted 5ms 372.0 KiB#include<bits/stdc++.h> int a[20005],len; using namespace std; int get() { int min,now,son,le,ri,t; min=a[1]; a[1]=a[len]; a[len]=0; len--; now=1; while(now*2<=len) { le=now*2; ri=now*2+1; if (ri>len) son=le; else { if (a[le]<a[ri]) son=le; else son=ri; } if (a[now]>a[son]) { t=a[now]; a[now]=a[son]; a[son]=t; now=son; } else break; } return min; } void put(int x) { int now,fa,t; len++; a[len]=x; now=len; fa=now/2; while (now!=1) { if (a[now]<a[fa]) { t=a[now]; a[now]=a[fa]; a[fa]=t; now=fa; fa=now/2; } else break; } } int main() { int n,ans; int i,j,tmp,x,y; cin>>n; len=1; ans=0; cin>>a[1]; for(i=2;i<=n;i++) { cin>>tmp; put(tmp); } while (len>1) { x=get(); y=get(); ans=ans+x+y; put(x+y); } cout<<ans; return 0; } -
0
想了很久，冒泡排序两次去找最小值和次小值。
用代码空间复杂度换取时间和内存的优势。
记录详情
Accepted状态 耗时 内存占用
#1 Accepted 324ms 372.0 KiB
#2 Accepted 3ms 360.0 KiB
#3 Accepted 5ms 352.0 KiB
#4 Accepted 9ms 356.0 KiB
#5 Accepted 66ms 384.0 KiB
#6 Accepted 116ms 372.0 KiB
#7 Accepted 279ms 460.0 KiB
#8 Accepted 329ms 256.0 KiB
#9 Accepted 206ms 356.0 KiB
#10 Accepted 325ms 340.0 KiB
代码
#include<iostream>
using namespace std;
#include<algorithm>
int sortNum;
int num[10000] = { 0 };
int AsmMinNum = 0;
int calMinEx()
{
for (int i = 0; i<sortNum - 1; i++)
{
for (int j = 1; j <= 2; j++)
{
if (i == 0) continue;
for (int k = sortNum -1; k > 0; k--)
{
if (num[k] == 0) continue;
if (num[k - 1] == 0)
{
num[k - 1] = num[k];
num[k] = 0;
}
else if (num[k] < num[k - 1])
{
int temp = num[k];
num[k] = num[k - 1];
num[k - 1] = temp;
}
}
}
AsmMinNum += num[0] + num[1];
num[1] = num[0] + num[1];
num[0] = 0;
}
return AsmMinNum;
}
int main()
{
cin >> sortNum;
for (int i = 0; i<sortNum; i++) cin >> num[i];
sort(num, num + sortNum);
cout << calMinEx() << endl;
return 0;
}
分数100总耗时1667ms峰值内存460.0 KiB -
0
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;void least_two(vector<long long> &v);
int main()
{
vector<long long> v;
int num;
cin >> num;
for (int i = 0; i < num; i++)
{
long long temp;
cin >> temp;
v.push_back(temp);
}least_two(v);
long long re = 0;
while (v.size()>1)
{
v[1] += v[0];
re += v[1];
v.erase(v.begin());
least_two(v);
}cout << re;
system("pause");
return 0;
}void least_two(vector<long long> &v)
{
for (unsigned int i = 0; i < v.size(); i++)
{
if (v[0] > v[i])
{
long long temp = v[0];
v[0] = v[i];
v[i] = temp;
}
}
for (unsigned int i = 1; i < v.size(); i++)
{
if (v[1] > v[i])
{
long long temp = v[1];
v[1] = v[i];
v[i] = temp;
}
}
} -
0
本来想每次加完都排一次，结果运行时间超出了。。。只好插入排序
#include<stdio.h>
void px(long int k,long int n,long int g[])//从小到大排序
{
for(int i=k;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(g[i]>g[j])
{
g[0]=g[i];g[i]=g[j];g[j]=g[0];}
}
}
int main()
{
long int g[10000]={0},n;
long int sum=0;
scanf("%ld",&n);
for(int i=1;i<=n;i++)
{
scanf("%ld",&g[i]);
}
px(1,n,g);
for(int k=2;k<=n;k++)
{
g[k]=g[k-1]+g[k];
sum+=g[k];
if(g[k]>g[k+1])
{
for(int i=k;i<=n-1;i++)//将g[k]插入到合适位置
{
if(g[i]<g[i+1])break;
g[0]=g[i];g[i]=g[i+1];g[i+1]=g[0];
}
}
}
printf("%ld",sum);
return 0;
} -
0
//优化了一点点
#include <iostream>
using namespace std;int main(int argc, char const *argv[])
{
std::ios_base::sync_with_stdio(false);
int n,min_phy = 0;
int fruit[10001];
cin>>n;
for(int i = 0; i < n; i++) {
cin>>fruit[i];
}
int fmin = fruit[0] > fruit[1]? 1 : 0;//最小值
int smin = fruit[1] <= fruit[0]? 0 : 1;//次小值
int pos = 0;
for(int i = 1; i < n; i++) {
for(int j = pos; j < n; j++) {//每次从pos开始搜索而不是从头
if(fruit[j] < fruit[fmin]) {
smin = fmin;
fmin = j;
}
else if(fruit[j] < fruit[smin] && j != fmin)
smin = j;
}
min_phy += fruit[fmin] + fruit[smin];
fruit[fmin] += fruit[smin];
swap(fruit[smin],fruit[pos++]);
fmin = fruit[pos] > fruit[pos+1]? pos+1 : pos;
smin = fruit[pos] > fruit[pos+1]? pos : pos+1;
}
cout << min_phy;
return 0;
} -
0
再发个简单的优先队列
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >p;//小的优先出的
int n;
int a,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
p.push(a);
}
while(p.size()!=1)
{
int d=p.top(); p.pop();
int b=p.top(); p.pop();
int c=d+b; p.push(c);
sum+=c;
}
cout<<sum;
return 0;
} -
0
没错此题是裸题
就是优先队列
而已
。#include<iostream> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> >q; int n; int main() { cin>>n; for(int i=1;i<=n;i++) { int tmp; cin>>tmp; q.push(tmp); } int ans=0; for(int i=1;i<n;i++) { int x=q.top(); q.pop(); int y=q.top(); q.pop(); int tmp2=x+y; ans+=tmp2; q.push(tmp2); } cout<<ans; } -
0
#include<bits/stdc++.h>
using namespace std;
int n,ans,k,maxn;
int num[10008],sum[10008];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
num[n+1]=0;
sort(num+1,num+1+n);
while(1)
{
int flag=0;
ans=num[1]+num[2];
sum[k]=ans;
if(k==n-1)
{
for(int i=0;i<k;i++)
maxn+=sum[i];
cout<<maxn;
return 0;
}
for(int i=3;i<=n-k;i++)
{
if(ans>num[i])
num[i-2]=num[i];
else
{
flag=1;
num[i-2]=ans;
for(int j=i-1;j<=n-k;j++)
num[j]=num[j+1];
break;
}
}
if(!flag) num[n-k-1]=ans;
k++;
}
return 0;
}
pipixue
LV 7
@ 2018-06-11 10:40:20
