努力把平凡的日子堆砌成伟大的人生

第一题 简单贪心

题目意思：你有n个u盘，以及内存为m的文件，可以分开装到不同的u盘里面最少需要几个

解题思路：我们要使用的最少,那我肯定优先使用最大的就是最优的

时间复杂度：o(nlogn) 排序

int t,n,m;

void solve()
{
    cin>>n>>m;
    vector<int> a(n);
    for(auto&v:a) cin>>v;
    sort(a.begin(),a.end(),greater<int>());
    int sum=0,cnt=0;
    for(auto&v:a){
        sum+=v;
        cnt++;
        if(sum>=m) break;
    }
    cout<<cnt<<endl;
    return ;
}

第二题 简单组合数

题目意思：给定你n本书,一共有m种类型,可以选择两本书,如果的书是不同类型的算一次贡献，求总贡献

解题思路：明显的类似排列组合第一种树可以和后面所有的书组合，后面的就不能和前面的组合

时间复杂度：o(nlogn)  mp

void solve()
{
    cin>>n>>m;

    map<int,int> mp;   
    vector<int> a(n);
    for(auto&v:a){
        cin>>v;
        mp[v]++;
    }
    int sum=n,ans=0;
    for(auto&v:a){
        mp[v]--;
        sum--;
        ans+=sum-mp[v];// 除了自己之外和后面所有和自己类别不一样的书进行组合
    }
    cout<<ans<<endl;
    return ;
}

第三题 +1-1的典型操作

题目意思：给定一个序列，每一次操作可以使得任意一个位置+1，其他一个位置-1
求使得最大值-最小值最小的最少操作次数

解题思路：典型的+1 -1 具有一个很明显的特点就是总和是永远不变的,那么我们要使得
最大值和最小值的差值最小明显的就是让所有数趋近于平均值即可,也就是最大值-最小值
<=1,那我们如何使得操作次数最少呢？最后每一个数要么是平均值,要么是平均值+1,明显的
思路是优先最大的变成平均值+1即可

时间复杂度：o(nlogn) 排序

void solve()
{
    cin>>n;
    int sum=0;
    vector<int> a(n); 
    for(auto&v:a) cin>>v,sum+=v;
    int m=sum/n,pos=sum%n;
    int ans=0;
    sort(a.begin(),a.end(),greater<int>());
    for(int i=0;i<n;i++){
        if(i<pos) ans+=abs(a[i]-m-1);
        else ans+=abs(a[i]-m);
    }   
    cout<<ans/2<<endl;
    return ;
}

第四题 最优策略的选择

题目意思：你要买k个工具，具有s元钱,给定n天兑换美元和英镑的汇率,以及m个物品
需要使用的货币购买以及费用,求解最早可以说明时候购买,并且买的每一个商品的编号以及购买时间

解题思路：首先我们现需要发现题目的性质,1.晚买的话一定不会比早买差,因为我可以使用之前的汇率去兑换就好了,所以我们发现具有前2.缀性，也就是汇率可以用有前缀最小值,同时我们维护一个下标,表示当前最优是那一天,接着我们利用1，可以发现具有了二分的性质,
所以我们可以使用二分来进行筛选时间,接着每一次都按照最优的来给每一个商品的价格来排序，选择前k个即可

时间复杂度：o(nlognlogn) 二分+内置排序 对于1e5范围这个时间复杂度是ok的

void solve()
{
    cin>>n>>m>>k>>s;
    vector<int> a(n+1),b(n+1),ida(n+1),idb(n+1);
    vector<PII> op(m+1),ans(k);

    a[0]=b[0]=2e9;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        if(x<a[i-1]){
            a[i]=x;
            ida[i]=i;
        }
        else{
            a[i]=a[i-1];
            ida[i]=ida[i-1];
        }
    }
   for(int i=1;i<=n;i++){
        int x; cin>>x;
        if(x<b[i-1]){
            b[i]=x;
            idb[i]=i;
        }
        else{
            b[i]=b[i-1];
            idb[i]=idb[i-1];
        }
    }
    for(int i=0;i<m;i++){
        int x,y; cin>>x>>y;
        op[i]={x,y};
    }
    //找到前缀的最小值

    auto check = [&](int mid){
        int x=a[mid],idx=ida[mid];
        int y=b[mid],idy=idb[mid];

        vector<PII> res(m);
        vector<int> cnt(m);
        for(int i=0;i<m;i++){
            auto [t,p]=op[i];
            if(t==1) res[i]={p*x,i};//记录此时需要多少元
            else res[i]={p*y,i};
        }
        sort(res.begin(),res.end());// 从小到大排序即可
        int need=0;
        for(int i=0;i<k;i++){
            auto [p,d]=res[i];
            need+=p;
            ans[i]={res[i].second+1,op[res[i].second].first == 1 ? idx : idy};
        }// 同时存下购买时间
        return need <= s ; 
    };

    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    // 当二分的值可能是不存在的时候我们可以利用此时的l来再次check一次即可
    if(!check(l)) cout<<-1<<endl;
    else{
        cout<<l<<endl;
        for(int i=0;i<k;i++){
            auto [x,d]=ans[i];
            cout<<x<<' '<<d<<endl;
        }
    }

    return ;
}

第五题 lca的直接考察

题目意思：给定n个点,m条边,求带上每一条边之后的生成树的值最小

解题思路：构造最小生成树,然后维护边和边的最大值,lca求解即可

struct code{
    int a,b,w,id;
    bool operator<(const code&t){
        return w<t.w;
    }
};

vector<PII> g[N];

void solve()
{
    cin>>n>>m;
    vector<code> edge(m+1);
    vector<int> p(n+1),depth(n+1,0x3f3f3f3f);
    vector<array<int,21>> fa(n+1);
    vector<array<int,21>> fv(n+1);
    int sum=0;

    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=1;i<=m;i++){
        int a,b,w; cin>>a>>b>>w;
        edge[i]={a,b,w,i};
    }

    sort(edge.begin()+1,edge.end());


    auto add = [&](int a,int b,int w){
        g[a].push_back({b,w});    
    };

    function<int(int)> find = [&](int x){
        if(x!=p[x]) p[x]=find(p[x]);
        return p[x];
    };

    auto kuskra = [&](){
        for(int i=1;i<=m;i++){
            auto [a,b,w,_]=edge[i];

            int fa=find(a),fb=find(b);
            if(fa!=fb){
                add(fa,fb,w); 
                add(fb,fa,w);
                sum+=w;
                p[fa]=fb;
            }
        }
    };

    kuskra();


    auto bfs = [&](){

      queue<int> q;
      depth[0]=0,depth[1]=1;
      q.push(1);
      while(!q.empty()){
          auto t=q.front(); q.pop();
          for(auto&[v,w]:g[t]){

              if(depth[v]>depth[t]+1){
                  depth[v]=depth[t]+1;
                  q.push(v);
                  fa[v][0]=t;
                  fv[v][0]=max(fv[v][0],w);
                  for(int k=1;k<=20;k++){
                      fv[v][k]=max(fv[v][k-1],fv[fa[v][k-1]][k-1]);
                      fa[v][k]=fa[fa[v][k-1]][k-1];
                  }
              }
          }
      }
    };
    bfs();

    auto lca = [&](int a,int b){
        int ans=0;
        if(depth[a]<depth[b]) swap(a,b);
        for(int k=20;k>=0;k--)
            if(depth[fa[a][k]]>=depth[b]){
                ans=max(ans,fv[a][k]);
                a=fa[a][k];
            }

        if(a==b) return ans;

        for(int k=20;k>=0;k--)
            if(fa[a][k]!=fa[b][k]){
                ans=max(ans,fv[a][k]);
                ans=max(ans,fv[b][k]);
                a=fa[a][k];
                b=fa[b][k];
            }
        return max({ans,fv[a][0],fv[b][0]});
    };

    vector<int> ans(m+1);

    for(int i=1;i<=m;i++){
        auto [a,b,w,id]=edge[i];
        ans[id]=sum+w-lca(a,b);
    }

    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return ;
}