Educational Codeforces Round 52 (Rated for Div. 2)

题目链接

B:
边最少点最多的方式是2个点一条边，不连通，边最多点最少的方式是完全图，边数为(n*(n-1)/2)

#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;



void run_case() {
    LL n, m, mn, mx = 0;
    cin >> n >> m;
    mn = max(0LL, n-2*m);
    for(LL i = 0; ; ++i) {
        if((i-1)*i/2 >= m) {
            mx = n - i;
            break;
        }
    }
    cout << mn << " " << mx;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.flags(ios::fixed);cout.precision(9);
    //int t; cin >> t;
    //while(t--)
    run_case();
    cout.flush();
    return 0;
}

C:
利用差分，一层一层贪心去除即可

#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int maxn = 2e5+5;
LL a[maxn];

void run_case() {
    int n;
    LL k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        a[0]++, a[x+1]--;
    }
    for(int i = 1; i < maxn; ++i)
        a[i] += a[i-1];
    int tmp = 0, ans = 0;
    for(int i = maxn-1; i >= 0; --i) {
        if(a[i] == n) break;
        if(tmp + a[i] > k) {
            tmp = a[i];
            ans++;
        } else 
            tmp += a[i];
    }
    if(tmp > 0) ans++;
    cout << ans;
    
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.flags(ios::fixed);cout.precision(9);
    //int t; cin >> t;
    //while(t--)
    run_case();
    cout.flush();
    return 0;
}