Codeforces Round #408 (Div. 2)C. Bank Hacking（STL）

题目链接：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 ;

 }

巴特西

Codeforces Round #408 (Div. 2)C. Bank Hacking（STL）

最新文章

热门文章