题目链接：http://codeforces.com/problemset/problem/796/C
题目大意：有n家银行，第一次可以攻击任意一家银行（能量低于自身），跟被攻击银行相邻或者间接相邻（距离<=2）的银行能量+1，除了第一次外，攻击一家银行需要满足以下条件：
①：跟被攻击过后的银行相邻；
②：能量低于攻击者
③：银行没有被攻击过
题解：可以从题意得知，比如攻击银行i，如果说银行i能量为t,跟银行距离>=2的银行中能量最大的为mx,自身至少所需能量=max(t+1,mx+2)，因为其他银行能量最多也只能+2；
这样，我们只需要遍历1~n家银行找到最少需要的能量就可以了；
这里我们用了两个c++数据结构,vector和multiset。vector属于<vector>是动态数组，multiset属于<set>会自动将里面的数字按从小到大排好；
#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
using namespace std;
const int N=3e5+;
vector<int>v[N];
multiset<int>ms; int main(){
int n,a,b;
int arr[N];
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",arr+i);
ms.insert(arr[i]);
}
for(int i=;i<=n-;i++){
scanf("%d %d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
int ans=<<;
multiset<int>::iterator it;
for(int i=;i<=n;i++){//遍历n家银行，找到需要最少能量的银行
//存下银行i的值后，在ms中删除
int temp=arr[i];
ms.erase(ms.find(arr[i]));
//找到跟i相邻的银行，比较后，在ms中删除
for(int j=;j<v[i].size();j++){
int k=v[i][j];
temp=max(temp,arr[k]+);
ms.erase(ms.find(arr[k]));
}
//比较距离大于2的银行能量最大值+2和temp的大小，保证每个银行都可以攻击
if(!ms.empty()){
it=ms.end();
temp=max(temp,*(--it)+);//由于ms.end()指向最后一位,而不是最后一个元素所以--it;
}
//还原ms中删除的元素
ms.insert(arr[i]);
for(int j=;j<v[i].size();j++){
int k=v[i][j];
ms.insert(arr[k]);
}
ans=min(temp,ans);//找到所有情况中最少的能量
}
printf("%d\n",ans);
}
另外附上一种贪心写法：
C1为mx个数 C2为mx-1个数
ans=mx 只有当C1=1&&正好有C2个mx-1与mx相连
ans=mx+1 只有当存在一个点满足 其距离<=1内 mx的个数为C1
其余情况ans=mx+2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll inf=1e10;
const int N=2e6+;
ll n,a[N],vis[N],can[N];
vector<int> e[N];
void solve()
{
ll C1=,C2=,mx=-inf,u;
for(int i=;i<=n;i++)
mx=max(a[i],mx);
for(int i=;i<=n;i++)
{
if(a[i]==mx)
C1++,u=i;
else if(a[i]==mx-)
C2++;
}
ll ans=inf;
if(C1==)//
{
int cnt=;
for(int i=;i<e[u].size();i++)
{
int v=e[u][i];
if(a[v]==mx-)
cnt++;
}
if(cnt==C2)
ans=mx;
}
if(ans==inf)
{
for(int i=;i<=n&&ans==inf;i++)//遍历边O(n),找到相邻为1内,有C1个mx
{
ll res=;
if(a[i]==mx)
res++;
for(int j=;j<e[i].size();j++)
{
int v=e[i][j];
if(a[v]==mx)
res++;
}
if(res==C1)
ans=mx+;
}
}
if(ans==inf)
ans=mx+;
cout<<ans<<endl;
}
int main()
{
while(cin>>n)
{
for(int i=;i<=n;i++)
scanf("%I64d",&a[i]),e[i].clear();
int u,v;
for(int i=;i<=n-;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
solve();
}
return ;
}