贪心 (Week 6）

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;
}

---

不足：

优先队列是个啥东西。

看了非常多题解。