选择数字

选择数字

#include <bits/stdc++.h>

using namespace std;

int n,ans1,ans2;

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int u;
        scanf("%d",&u);
        ans1=max(ans1,u);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int u;
        scanf("%d",&u);
        ans2=max(ans2,u);
    }
    printf("%d %d",ans1,ans2);
    return 0;
}

最大中位数

最大中位数

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n,k,a[N];

bool check(ll x) {
    ll res=0;
    for(int i=n/2+1;i<=n;i++)   //在[n/2+1,n]中计算个数
      if(a[i]<x)
        res+=abs(a[i]-x);
    return res<=k;
}

int main() {
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
      scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll l=1,r=*max_element(a+1,a+n+1)+k;
    while(r>l) {    //二分答案
        ll mid=l+r+1>>1;
        if(check(mid))
          l=mid;
        else
          r=mid-1;
    }
    printf("%lld",l);
    return 0;
}

数字移动

数字移动

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+5;

int T,n,p[N];
int v[N],c[N];

int main() {
    scanf("%d",&T);
    while(T--) {
        memset(v,0,sizeof(v));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%d",&p[i]);
        for(int i=1;i<=n;i++) { //置换的拆分
            if(v[i])
              continue;
            int j=i,num=0;
            do {    //搜索当前的环
                j=p[j];
                num++;
                v[j]=i; //将当前环全部用一个编号表示
            }while(j!=i);
            c[i]=num;   //这个编号的环的大小是num
        }
        for(int i=1;i<=n;i++)
          printf("%d ",c[v[i]]);
        puts("");
    }
    return 0;
}