contest 1.25

B.指引

排序+贪心+set

#include <iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
 
struct Node{int x,y;}a[100005],b[100005];
 
bool cmp(Node a,Node b){
  return a.x>b.x;
}
 
set<int> s;
set<int>::iterator it;
 
int main()
{
    int num;scanf("%d",&num);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++) scanf("%d%d",&b[i].x,&b[i].y);
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    int ans=0;
    for(int i=1,j=1;i<=n;){
        while(j<=n&&b[j].x>a[i].x) s.insert(b[j].y),j++;
        it=s.lower_bound(a[i].y);
        if(it==s.end()) i++;
        else s.erase(*it),ans++,i++;
    }
    printf("%d
",ans);
    return 0;
}

D.报名签到

#include <iostream>
#include<cstdio>
typedef long long ll;
using namespace std;
 
int a[100005];
 
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ll ans=0;
    for(int i=1;i<=n-1;i++){
        ans+=max(a[i],a[i+1]);
    }
    printf("%lld
",ans);
    return 0;
}

F.分组

贪心 (数据水

#include <iostream>
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
 
int a[100005];
 
struct Q{
  int last,len;
}q[100005];
int cnt=0;
 
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(cnt==0) q[++cnt].last=a[i],q[cnt].len=1;
        else{
            int f=-1,minn=inf;
            for(int j=1;j<=cnt;j++){
                if(q[j].last+1==a[i]&&q[j].len<minn){
                    minn=q[j].len;
                    f=j;
                }
            }
            if(f==-1) q[++cnt].last=a[i],q[cnt].len=1;
            else q[f].last=a[i],q[f].len++;
        }
    }
    int ans=inf;
    for(int i=1;i<=cnt;i++) ans=min(ans,q[i].len);
    printf("%d
",ans);
    return 0;
}