Codeforces Codeforces Round #408 (Div. 2) Bank Hacking（数据结构）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<set>
 4 #include<vector>
 5 using namespace std;
 6 const int N=3e5+5;
 7 vector<int>v[N];
 8 multiset<int>ms;
 9 
10 int main(){
11     int n,a,b;
12     int arr[N];
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++){
15         scanf("%d",arr+i);
16         ms.insert(arr[i]);
17     }
18     for(int i=1;i<=n-1;i++){
19         scanf("%d %d",&a,&b);
20         v[a].push_back(b);
21         v[b].push_back(a);
22     }
23     int ans=1<<30;
24     multiset<int>::iterator it;
25     for(int i=1;i<=n;i++){//遍历n家银行，找到需要最少能量的银行 
26         //存下银行i的值后，在ms中删除 
27         int temp=arr[i];
28         ms.erase(ms.find(arr[i]));
29         //找到跟i相邻的银行，比较后，在ms中删除 
30         for(int j=0;j<v[i].size();j++){
31             int k=v[i][j];
32             temp=max(temp,arr[k]+1);
33             ms.erase(ms.find(arr[k]));
34         }
35         //比较距离大于2的银行能量最大值+2和temp的大小，保证每个银行都可以攻击 
36         if(!ms.empty()){
37             it=ms.end();
38             temp=max(temp,*(--it)+2);//由于ms.end()指向最后一位,而不是最后一个元素所以--it; 
39         }
40         //还原ms中删除的元素 
41         ms.insert(arr[i]);
42         for(int j=0;j<v[i].size();j++){
43             int k=v[i][j];
44             ms.insert(arr[k]);
45         }
46         ans=min(temp,ans);//找到所有情况中最少的能量 
47     }
48     printf("%d\n",ans);
49 } 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef pair<ll,ll> ii;
 5 const ll inf=1e10;
 6 const int N=2e6+20;
 7 ll n,a[N],vis[N],can[N]; 
 8 vector<int> e[N];
 9 void solve()
10 {
11     ll C1=0,C2=0,mx=-inf,u;
12     for(int i=1;i<=n;i++)
13         mx=max(a[i],mx);
14     for(int i=1;i<=n;i++)
15     {
16         if(a[i]==mx)
17             C1++,u=i;
18         else if(a[i]==mx-1)
19             C2++; 
20     }
21     ll ans=inf;
22     if(C1==1)//
23     {
24         int cnt=0;
25         for(int i=0;i<e[u].size();i++)
26         {
27             int v=e[u][i];
28             if(a[v]==mx-1)
29                 cnt++;
30         }
31         if(cnt==C2)
32             ans=mx;
33     }
34     if(ans==inf)
35     {
36         for(int i=1;i<=n&&ans==inf;i++)//遍历边O(n),找到相邻为1内,有C1个mx  
37         {
38             ll res=0;
39             if(a[i]==mx)
40                 res++;
41             for(int j=0;j<e[i].size();j++)
42             {
43                 int v=e[i][j];
44                 if(a[v]==mx)
45                     res++;
46             }
47             if(res==C1)
48                 ans=mx+1;
49         }
50     }
51     if(ans==inf)
52         ans=mx+2;
53     cout<<ans<<endl;
54 }
55 int main()
56 {
57     while(cin>>n)
58     {
59         for(int i=1;i<=n;i++)
60             scanf("%I64d",&a[i]),e[i].clear();
61         int u,v;
62         for(int i=1;i<=n-1;i++)
63         {
64             scanf("%d%d",&u,&v);
65             e[u].push_back(v);
66             e[v].push_back(u);
67         }
68         solve();
69     }
70     return 0;
71 }