QFNU 10-02 19 training 补题

C - From S To T

给一个图，‘.’表示白色，‘*’表示黑色，一次填充使一个白色变成黑色，找出缺少黑色最少的行列

记录每一行，每一列白色的个数，循环找出行列和最小的那一组

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a[50010];
    int t;
    cin>>t;
    while(t--)
    {
        int h[50010]= {0},l[50010]= {0};
        int n,m,i,j;
        cin>>n>>m;
        for(i=0; i<n; i++)
        {
            cin>>a[i];
            for(j=0; j<m; j++)
            {
                if(a[i][j]=='.')
                {
                    h[i]++;
                }
            }
        }
        for(j=0; j<m; j++)
        {
            for(i=0; i<n; i++)
            {
                if(a[i][j]=='.')
                {
                    l[j]++;
                }
            }
        }
        int ans=0,minn=999999;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(a[i][j]=='.')
                {
                    ans=-1;
                }else{
                    ans=0;
                }
                minn=min(h[i]+l[j]+ans,minn);
            }
        }
        cout<<minn<<endl;

    }
}

F - Coffee Break

某人要在n天内喝n杯咖啡，每杯咖啡都要在一天特定的时间喝掉，如果两杯咖啡在一天喝，那么它们之间至少要相隔d min，要求输出最少几天可以喝完，并输出对应题目输入的每一杯咖啡是在第几天喝的

#include <bits/stdc++.h>
using namespace std;
int a[100100],b[100100];
set<pair<int,int> >se;
int main()
{
    int n,m,d,i;
    cin>>n>>m>>d;
    for(i=0;i<n;i++){
        cin>>a[i];
        se.insert(make_pair(a[i],i));
    }
    int cnt=0，pos;
    while(!se.empty()){
        pos =se.begin()->second;
        b[pos]=++cnt;
        se.erase(se.begin());
        while(1){
            auto t=se.lower_bound({a[pos]+d+1,0});
            //lower_bound(begin,end,i)用法是查找排好序的从begin开始到end结束不大于i的数，二分查找方法
            if(t==se.end())
                break;
            pos=t->second;
            b[pos]=cnt;
            se.erase(t);
        }
    }
    cout<<cnt<<endl;
    cout<<b[0];
    for(i=1;i<n;i++){
        cout<<' '<<b[i];
    }
    return 0;
    
}