牛客挑战赛74题解

A：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e6+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
#define CY cout<<"YES"<<'\n'
#define CN cout<<"NO"<<'\n'
signed main()
{
    //模板和手速训练
int n;
cin>>n;
//一共可以拿走n/2个
//大概就是2个必须拿走1个，
rep(i,1,n)
{
    cin>>a[i];
}
int ans=0;
rep(i,1,n)
{
    if(i&1)
    {
        ans+=max(a[i],a[i+1]);
    }
    else
    {
        continue;
    }
}
cout<<ans;
    return 0;

}

B:

本题有两种做法：

第一种：排序用set进行二分查找，然后删除，复杂度nlogn

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
#define CY cout<<"YES"<<'\n'
#define CN cout<<"NO"<<'\n'
int b[N];
multiset<int>s;
int main()
{
    ios;
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ans=0;
multiset<int>::iterator it;
    rep(i,1,m)
    {
        cin>>b[i];
        if(b[i]>=a[1])
        s.insert(b[i]); 
    }
rep(i,1,n)
{
 it=s.lower_bound(a[i]);
 if(it==s.end())
 {
break;
 }
 else
 {
    ans++;
    s.erase(it);
 }
}
cout<<ans;
}

第二种：双指针，复杂度nlogn，比较

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
const int N=1e6+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
#define CY cout<<"YES"<<'\n'
#define CN cout<<"NO"<<'\n'
int b[N];
multiset<int>s;
int main()
{
ios;
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
sort(a+1,a+1+n);
rep(i,1,m)
{
    cin>>b[i];
}
sort(b+1,b+1+m);
int j=1;
int ans=0;
rep(i,1,n)
{
while(b[j]<a[i]&&j<=m)
{
    j++;
}
if(j>m)
{
    break;
}
if(b[j]>=a[i])
{
    ans++;
    j++;
}
}
 
cout<<ans;
 
}

C:

究极分类讨论题

对于该问题需要考虑所有可能的情况在注释中，可针对注释进行细品。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;cin >> T;
    while(T--){
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        long long ans = max(a + b, c + d);
        // A D
        ans = min({ans, max(max(a, d) + b / 2, max(a, d) + c / 2)});
        // B C
        ans = min({ans, max(max(b, c) + a / 2, max(b, c) + d / 2)});
        // A B
        ans = min(ans, a + max(c / 2, b) + d / 2);
        ans = min(ans, b + max(d / 2, a) + c / 2);
        // C D
        ans = min(ans, c + max(a / 2, d) + b / 2);
        ans = min(ans, d + max(b / 2, c) + a / 2);

        ans = min(ans, max(a + b, max(a, d) + c / 2));
        ans = min(ans, max(a + b, max(c, b) + d / 2));
        ans = min(ans, max(c + d, max(b, c) + a / 2));
        ans = min(ans, max(c + d, max(a, d) + b / 2));
        cout << ans << "\n";
    }
}

D:

一定是需要一个数据结构进行维护的

至于是什么呢，set就很好

#include<bits/stdc++.h>
using namespace  std;
using i64 = long long;
int main()
{
    i64 n,m,k;
    cin >> n >> m >> k;
    vector<i64> a(n + 1),b(n + 1),hp(n + 1);
    set<pair<i64,i64>> se;
    i64 sum = 0,old = 0;
    for(int i = 1;i <= n; i  ++)
        cin >> a[i];
    for(int i = 1;i <= n ;i  ++)
        cin >> b[i];
    int cnt = n;
    for(int i = 1;i <= n; i ++)
    {        
        hp[i] = b[i];
        se.insert({b[i],i});
        sum += a[i];
    }
    while(k --)
    {
        int op;cin >> op;
        if(op == 1)
        {
            int x;
            cin >> x;
            sum += a[x];
            se.insert({hp[x] = old + b[x],x});
        }
        else if(op == 2)
        {
            int x;
            cin >> x;
            sum -= a[x];
            se.erase({hp[x],x});
        }
        else if(op == 3)
        {
            int y;
            cin >> y;
            old += y;
            while(se.size()&&se.begin() -> first <= old)
            {
                cnt --;
                sum -= a[se.begin()->second];
                se.erase(se.begin());
            }
        }
        else
        {
            int x,h;
            cin >> x >> h;
            se.erase({hp[x],x});
            se.insert({hp[x] = min(old + b[x],hp[x] + h),x});
        }
        m -= sum;
        if(m <= 0)break;
    }
    if(m > 0){
        cout <<"NO\n";
    }else {
        cout <<"YES\n";
        cout << cnt <<"\n";
    }
}