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