Codeforces Round #509 (Div. 2)

A. Heist
题意：找出最大数和最小数之前缺少了多少个数
题解：排序之后直接计算

#include <bits/stdc++.h>

const int MAXN = 10000;

using namespace std;

int N,sum;
int a[MAXN];

int main()
{
    scanf("%d",&N);
    
    for(int i = 1;i <= N;i++){
        scanf("%d",&a[i]);
    }
    
    sort(a+1,a+N+1);
    
    sum = a[N] - a[1] - N + 1;
    printf("%d\n",sum);
    return 0;
} 

B. Buying a TV Set
题意：电视的尺寸比例是xy的，问你在ab的墙上可以挂多少种不同尺寸的电视
题解：先化简x/y，然后分别用长和宽去处于a和b取较小的值

#include <bits/stdc++.h>

using namespace std;

long long a,b,x,y,gc;
long long c,d;

int main()
{
    scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
    gc = __gcd(x,y);
    x /= gc;y /= gc;
    c = a / x;
    d = b / y;
    printf("%lld\n",min(c,d));
    
    return 0;
} 

C. Coffee Break
有n个休息时刻，你需要把这n个休息时刻安排到尽量少的天中，使得每两个休息时刻的间隔大于d分钟，一天有m分钟。注意两天之间的间隔大于d分钟
题解：用set对时间排序，然后先取出一个时间然后取出大于d的时间，如果不存在就天数++

#include <bits/stdc++.h>

const int MAXN = 200005;

using namespace std;

int N,M,D,sum;
int Day[MAXN];

struct node{
    int val,id;
    friend bool operator < (const node &A,const node &B){
        return A.val < B.val;
    }
};

set<node>S;
set<node>::iterator it;

inline int read()
{
    int x = 0;char ch =  getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

int main()
{
    N = read();M = read();D = read();
    int v;
    for(int i = 1;i <= N;i++){
        v = read();
        S.insert((node){v,i});
    }    
        
    for(sum = 1;!S.empty();sum++){
        it = S.begin();
        Day[(*it).id] = sum;
        v = (*it).val; 
        S.erase(it);
        while(1){
            it = S.upper_bound((node){v+D,0});
            if(it ==  S.end()) break;
            Day[(*it).id] = sum;
            v = (*it).val;
            S.erase(it);
        }
    }
    printf("%d\n",sum-1);
    for(int i = 1;i <= N;i++) printf("%d ",Day[i]);
    return 0;
}

D. Glider
题意：你从H的高度往下落，下降的过程中存在N个平流层在平流层飞行高度不会变化(只会向X的正半轴平移而不会向Y轴负半轴平移)，如果不在平流层，则每次向X正半轴位移的同时，会向Y的负半轴平移
题解：计算从第一个平流层起点起飞，最远能到哪儿，然后计算到下个平流层需要起点往后多远

#include <bits/stdc++.h>

const int MAXN = 200005;

using namespace std;

int N,H,sum,ans,ql;

struct node{
    int L,R;
}C[MAXN];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void init(){
    N = read();H = read();
    
    for(int i = 1;i <= N;i++){
        C[i].L = read();C[i].R = read();
    }
    ql = 1;sum = C[1].R - C[1].L;
    for(int i = 2;i <= N;i++)
    {    
        if(H > C[i].L - C[i-1].R){
            H -= C[i].L - C[i-1].R;
            sum += C[i].L - C[i-1].R;
            sum += C[i].R - C[i].L;
            ans =  max(ans,sum+H);
            continue;
        }
        while(H < C[i].L - C[i-1].R + 1){
            if(ql == i) continue;
            H += C[ql+1].L - C[ql].R;
            sum -= C[ql+1].L - C[ql].R;
            sum -= C[ql].R - C[ql].L;
            ql++;
        }
        H -= C[i].L - C[i-1].R;
        sum += C[i].L - C[i-1].R;
        sum += C[i].R - C[i].L;
        ans =  max(ans,sum+H);
    }
    if(N == 1) ans = C[1].R - C[1].L + H;
}

int main(){
    init();
    printf("%d",ans);
    return 0;
}