这里写自定义目录标题

• 1012 Cyber Language
• 1009 Package Delivery

1012 Cyber Language

题目

​ 给定一串字符将首字母大写

分析

​ 遍历每个字符，如果一个字符是小写字母且前一个字符是空格或者它是第一个 字符，那么把它转大写输出

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e3+5,M=5e5+5;

int n,m;
string str;

int main(){
    int T;
    cin>>T;
    getchar();
    while(T--) {
        getline(cin,str);
        string ans="";
        for(int i=0;i<str.length();i++) {
            if(i==0) ans+=str[i]-32;
            else if(str[i]==' '&&i!=str.length()-1) ans+=str[i+1]-32;
        }
        cout<<ans<<endl;
    }
	return 0;
}

1009 Package Delivery

题目

​ 有n个包裹，在规定时间内可领取，一次最多能领k个包裹，问最少要取几次

分析

​ 考虑 r 最小的那个区间 k，第一次取快递放在第$r_{k}r\_k$天一定不会使结果变差。此时可能有很 多区间覆盖了 $r_{k}r\_k$，那么为了尽量延后下一次取快递的日期，此时的最优策略应该是选择覆盖$r_{k}r\_k$

​ r 值最小的 k 个区间，使用堆维护

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e5+5,M=5e5+5;

int n,m,k;
struct node{
    int l,r,id;
    bool operator < (const node &b) const {
        if(r==b.r) return l>b.l;
		return r > b.r; //从大到小
	}
};

struct node p[N],q[N];
bool st[N];

bool cmp1(struct node a,struct node b) {
    if(a.r==b.r) return a.l<b.l;
    return a.r<b.r;
}

bool cmp2(struct node a,struct node b) {
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}

int check() {
    int pos=1,pos2=1,t=0,r;
    priority_queue<node> heap;
    int cnt=0;
    while(pos<=n) {
        if(st[p[pos].id]) {
            pos++;
            continue;
        }
        st[p[pos].id]=1;
        r=p[pos].r;
        pos++; t++;
        while(pos2<=n) {
            if(st[q[pos2].id]) {
                pos2++;
                continue;
            }
            if(q[pos2].l>r) break;
            heap.push(q[pos2++]);
        }
        while(heap.size()&&t<k) {
            node tt=heap.top(); heap.pop();
            if(st[tt.id]||tt.r<r) continue;
            st[tt.id]=1;
            t++;
        }
        t=0;
        cnt++;
    }
    return cnt;
}

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--) {
       memset(st,0,sizeof(st));
       scanf("%d%d",&n,&k);
       //printf("%d %d\n",n,k);
       int a,b;
       for(int i=1;i<=n;i++) {
            scanf("%d%d",&a,&b);
            p[i]={a,b,i};
            q[i]={a,b,i};
       }
       sort(p+1,p+n+1,cmp1);
       sort(q+1,q+n+1,cmp2);
       printf("%d\n",check());
    }
	return 0;
}