Codeforces Round #544 (Div. 3) （A~D）

Codeforces Round #544 (Div. 3)

A. Middle of the Contest

题意：给两个时刻，求中间时刻。

思路：计算出总的分钟数/2即可，注意输出格式！

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d;
    scanf("%d:%d",&a,&b);
    scanf("%d:%d",&c,&d);
    int t1=a*60+b,t2=c*60+d;
    int sum=(t1+t2)/2;
    printf("%02d:%02d\n",sum/60,sum%60);
    return 0;
}

B. Preparation for International Women's Day

题意：有n个数，记作d[i].能够使用组成多少对，使得每一对的和都能整除k。求最后用到的数的个数。

思路：记录%k的数分别有多少个，计算对数即可，注意判断边界。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn],d[maxn];
int main(){
    int n,k,x;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>x,a[x%k]++;
    int res=a[0]/2;
    for(int i=1;i<k/2;i++){
        int minn=min(a[i],a[k-i]);
        res+=minn;
        a[i]-=minn;
        a[k-i]-=minn;
    }
    if(k%2==0) res+=a[k/2]/2;
    else res+=min(a[k/2],a[k-k/2]);
    cout<<res*2<<endl;
    return 0;
}

C. Balanced Team

题意：给n个数，可以从中选1~n个数，但是极差不能超过5，问最多可以选几个数。

思路：排序后 对于每一个数二分查找符合条件的，最后取max即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int>v;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    int res=0;
    for(int i=0;i<n;i++){
        int w=upper_bound(v.begin(),v.end(),v[i]+5)-v.begin();
        res=max(res,w-i);
    }
    cout<<res<<endl;
    return 0;
}

D. Zero Quantity Maximization

题意：给两个数组a,b，构造一个数组c，使得c[i]=a[i]*d+b[i]

找到一个d使得c数组有最多0，求出0的最多个数。

思路：

就是求斜率相同的最大个数，用map统计一下b/a的个数取max即可。

细节挺多的：1.要用long double 2.特判一下a==0或b==0的情况，如果a==0&&b==0直接加到结果里就好。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int a[maxn];
long double b[maxn];
map<long double,int>mp;

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int res=0,tmp=0;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            if(b[i]==0){
                tmp++;
            }
            continue;
        }
        long double x=b[i]/a[i];
        mp[x]++;
        res=max(res,mp[x]);
    }
    res+=tmp;
    cout<<res<<endl;
    return 0;
}