Round A - Kick Start 2019

a.链接：https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6

题意：有n个学生，要从里面选出p个来。每一个学生都有一个能力值。

要求你选出来的一组学生能力是相同的，有的学生能力比较低，所以需要花费你的时间来提升学生能力，一个学生提升1个能力值需要1小时。

求最低花费。

方法：因为只能提高学生的能力值，不能降低，所以一定是选择能力值挨着的那些。将数组排序，然后计算前p个花费，再将窗口往后移动...分别计算。

#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>

using namespace std;

static auto x = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
};

int main(){
    int t,n,p;

    cin>>t;
    int tmp=0;
    int ii=0;
    while(ii<t){
        cin>>n>>p;
        vector<int> si;
        for(int i=0;i<n;i++){
            cin>>tmp;
            si.push_back(tmp);
        }
        if(p==1){
            cout<<"Case #"<<++ii<<": "<<0<<endl;
            continue;
        }
        sort(si.begin(),si.end());
        int last=0;
        int minn=INT_MAX;
        for(int i=0;(i+p-1)<n;i++){
            if(i==0){
                for(int j=0;j<p;j++){
                    last += si[p-1]-si[j];
                }
            }else{
                last-=si[i+p-2]-si[i-1];
                last+=(si[i+p-1]-si[i+p-2])*(p-1);
            }
            minn=min(minn,last);
        }
        cout<<"Case #"<<++ii<<": "<<minn<<endl;
    }
    return 0;
}

View Code

b. https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/000000000006987d

没做出来啊，真是菜的不行....连题解都看不懂！！！

题意：r*c的方格，其中1表示邮局，0表示空地。每个空地都有个最短运输时间x(是所有的1到这个点的曼哈顿距离中最小的),总运输时间是每个空地最短运输时间最大的那个。让你添加一个邮局，求最小的总运输时间。(应该是这个意思吧。。。)

代码错误，只是暂时记录。

#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>

using namespace std;

static auto x = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
};

typedef struct locaa{
    int x,y;
} loca;

int main(){
    int t,r,c;

    cin>>t;
    int ii=0;
    char charr='0';
    while(ii<t){
        vector<loca> yi,ling;
        vector<int> lingdis;
        cin>>r>>c;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                cin>>charr;
                if(charr=='0'){
                    ling.push_back({i,j});
                    lingdis.push_back(INT_MAX);
                }else{
                    yi.push_back({i,j});
                }
            }
        }
        if(ling.size()==0){
            cout<<"Case #"<<++ii<<": "<<0<<endl;
            continue;
        }
        if(ling.size()==r*c){
            int midx,midy;
            if(r%2==1){
                midx=(r+1)/2;
            }else{
                midx=r/2;
            }
            if(c%2==1){
                midy=(c+1)/2;
            }else{
                midy=c/2;
            }
            int mhd=r-midx+c-midy;
            cout<<"Case #"<<++ii<<": "<<mhd<<endl;
            continue;
        }
        int maxx=INT_MIN;
        int x,y;
        for(int i=0;i<ling.size();i++){
            int minn=INT_MAX;
            for(int j=0;j<yi.size();j++){
                int dis=abs(ling[i].x-yi[j].x)+abs(ling[i].y-yi[j].y);
                minn=min(dis,minn);
            }
            lingdis[i]=minn;
            if(minn>maxx){
                maxx=minn;
                x=ling[i].x;
                y=ling[i].y;
            }
        }
        yi.push_back({x,y});
        int res=INT_MIN;
        for(int i=0;i<ling.size();i++){
            lingdis[i]=min(lingdis[i],abs(ling[i].x-x)+abs(ling[i].y-y));
            res=max(res,lingdis[i]);
        }

        cout<<"Case #"<<++ii<<": "<<res<<endl;
    }
    return 0;
}
/*
3
3 3
101
000
101
1 2
11
5 5
10001
00000
00000
00000
10001

*/