2020牛客暑假多校集训第八场（补题）

I – Interesting Computer Game
题目大意：
• 给了两个数组a与b。
• 第i步可以从a和b中选择一个数。
• 求最后选出的数中，不同的数要最多。
思路：我开始用map来模拟a与b数字的选择，但答案总是错误，实际上应该把不同的数当成图中的点。二元数组a，b当成是一条边，最后构成图，如果转化成图之后有的地方形成了环的话，说明其中的点多次出现，每个都可以取到，对于没有构成环的部分，可能有个点只出现过一次。（利用并查集来解）

#include<iostream>
#include<map>
using namespace std;
const int maxn=1e5+10，maxe=2e5+10;
map<int,int> mp;
int a[maxn],b[maxn];
bool vis[maxe];
int f[maxe],n;

int findfather(int x){
    if(x!=f[x])  f[x]=findfather(f[x]);
    return f[x];
}
void bin()
{
int x,y;
     for(int i=1;i<=n;i++){
            x=findfather(mp[a[i]]),y=findfather(mp[b[i]]);
            if(x!=y){
                f[x]=y;
                if(vis[x]||vis[y])  vis[y]=1,vis[x]=1;
            }
            else  vis[y]=1;
        }
}
int main(){
    int T;
    cin>>T;
    for(int k=1;k<=T;k++){
        int num=1;
       cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            if(!mp[a[i]])  mp[a[i]]=num++;
            if(!mp[b[i]])  mp[b[i]]=num++;
        }
        for(int i=1;i<=num;i++)  f[i]=i,vis[i]=0;
        bin();
        int ans=num-1;
        for(int i=1;i<num;i++){
            if(f[i]==i&&vis[i]==0)   ans--;
        }
         cout<<"Case #"<<k<<": "<<ans<<endl;
       mp.clear();
    }
}

I – Interesting Computer Game
题意：
• 有n种菜，每种菜的数量为bi, 每个菜的盈利为 ai。
• 每个顾客必须从第1种菜开始，连续地吃，每种吃一个。
• 保证顾客最多的情况下，盈利最大。
思路：
由题意可以，顾客最多的数量就是b1，而且将b数组处理，后面每一位都比前面的数小，之后就可以比较数组a的前缀和，取出最大的数，因为b数组处理后每一位都比前面的数小，我们从后往前枚举前缀和。因为long long会超出，使用long double。

#include<iostream>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
int t,n,a[maxn],b[maxn];
long double c[maxn];
int main(){
    cin>>t;
    for(int k=1;k<=t;k++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            c[i]=c[i-1]+a[i];
        }
        ll u=c[1];
        a[1]=1;
        for(int i=2;i<=n;i++){
            if(c[i]<=u)    a[i]=0;
            else{
                a[i]=1;
                u=c[i];
            }
        }
        b[0]=1e5+10;
        for(int i=1;i<=n;i++){
           cin>>b[i];
            b[i]=min(b[i-1],b[i]);
        }
        int l=0;
        long double ans=0;
        for(int i=n;i>=1;i--)
            if(a[i]!=0){
                ans+=c[i]*(b[i]-l);
                l=b[i];
            }
       printf("Case #%d: %d %.0Lf\n",k,b[1],ans);

    }
}