T1 三国游戏
每次选择都不可能选中最大默契值的武将，所以从1号到最后一号武将找与他默契值第二大的武将，并一直更新答案。
代码如下。
#include <iostream>
#include <algorithm>
using namespace std;
int g[505][505];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
cin>>g[i][j];
g[j][i]=g[i][j];
}
}
for(int i=1;i<=n;i++){
sort(g[i]+1,g[i]+n+1);
}
int ans=0;
for(int i=1;i<=n;i++){
if(g[i][n-1]>ans)
ans=g[i][n-1];
}
cout<<"1"<<endl<<ans;
return 0;
}T2 独木桥
是summer camp的一道题目。
两个士兵相遇调头可以视作穿了过去。
#include <iostream>
using namespace std;
const int N=5e3+5;
int num[N];
int maxs,mins;
int l,r;
int len,n;
int main(){
cin>>len>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
l=num[i];
r=len-num[i]+1;
if(l<r){
if(l>mins) mins=l;
if(r>maxs) maxs=r;
}
else{
if(r>mins) mins=r;
if(l>maxs) maxs=l;
}
}
cout<<mins<<' '<<maxs;
return 0;
}T3 排队接水
贪心的入门题？
代码如下。
#include <bits/stdc++.h>
using namespace std;
struct p{
int x;
int t;
};
int n;
double sum;
bool cmp(p a,p b){
return a.t<b.t;
}
p a[1005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t;
a[i].x=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
sum+=(a[i].t*(n-i));
cout<<a[i].x<<' ';
}
double ans = sum / n;
printf("\n%.2f",ans);
}T4 合并果子
要用到优先队列 priority_queue。(stl是个好东西。
要包含头文件 queue。
头为小元素的声明方式。
贪心策略是每次合并最小的两堆果子。
priority_queue< long long int , vector< long long int > , greater<long long int > #include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue< long long int , vector< long long int > , greater<long long int > >num;
long long int n,t,temp,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
num.push(t);
}
while(!num.empty()){
temp=num.top();
num.pop();
if(num.empty()){
break;
}
temp+=num.top();
num.pop();
ans+=temp;
num.push(temp);
}
cout<<ans;
return 0;
}不足：
优先队列是个啥东西。
看了非常多题解。