codeforces 796C Bank Hacking

题目链接：http://codeforces.com/contest/796/problem/C

题意：有n家银行，每家银行的防护强度是ai。然后给你n-1个连接，ui、vi表示两银行有连接。银行之间的关系有直接相连和间接相连两种。然后你现在要攻击所有的银行，你第一次可以攻击任意一个银行，接下来你必须攻击已经攻击过的银行的相邻的银行，并且你的电脑强度k要不小于银行防护强度。每当你攻击一个银行i，那么与i直接相连和间接相连的银行强度+1。问你的电脑强度k最小是多少，才能攻击掉所有的银行。

分析：首先我们可以发现，对于任意一个银行强度他最多增加2，因此我们可以把你的电脑强度的值缩小到mx,mx+1,mx+2之间，接下来我们就要分析每一种情况发生的条件。

　　对于mx发生的情况，你必须保证所有银行只有一个mx，如果多于一个必然是不行的。那么对于只有一个mx，是否有可能结果比mx大呢？答案是肯定的，比如你又一堆mx-1的强度，他们有的与mx间接相连，那么k就变成了mx+1；因此在有一个mx的情况下，所有mx-1都与他直接连接，结果就是max，否则结果是mx+1；

　　对于mx+1情况，除了上边以外，还有就是mx个数大于1，但是他们被同一个银行直接相连。

　　其他情况为mx+2。

AC代码：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long a[300005];
 5 vector<int >g[300005];
 6 int main() {
 7     ios_base::sync_with_stdio(0);
 8     cin.tie(0);
 9     int n;
10     int u,v;
11     long long mx=-1e10;
12     cin>>n;
13     for(int i=1;i<=n;i++){
14         cin>>a[i];
15         mx=max(a[i],mx);
16     }
17     for(int i=1;i<n;i++){
18         cin>>u>>v;
19         g[u].push_back(v);
20         g[v].push_back(u);
21     }
22     int number=0,number2=0;
23     for(int i=1;i<=n;i++){
24         if(a[i]==mx){
25             number++;
26         }
27         if(a[i]==mx-1){
28             number2++;
29         }
30     }
31     if(number==1){
32         int num=0;
33         for(int i=1;i<=n;i++){
34             if(a[i]==mx){
35                 int d=g[i].size();
36                 for(int j=0;j<d;j++){
37                     if(a[g[i][j]]==mx-1){
38                         num++;
39                     }
40                 }
41                 break;
42             }
43         }
44         if(num==number2) {
45             cout<<mx<<endl;
46         }
47         else cout<<mx+1<<endl;
48     }
49     else {
50         int num=0;
51         int p=0;
52         for(int i=1;i<=n;i++){
53             if(a[i]==mx){
54                 num=1;
55             }
56             else num=0;
57             int d=g[i].size();
58             for(int j=0;j<d;j++){
59                 if(a[g[i][j]]==mx){
60                     num++;
61                 }
62             }
63             if(num==number){
64                 p=1;
65                 break;
66             }
67         }
68         if(p==1) cout<<mx+1<<endl;
69         else cout<<mx+2<<endl;
70     }
71 
72 return 0;
73 }      

View Code

转载于:https://www.cnblogs.com/ls961006/p/6926205.html