Daliy Algorithm (greedy , hash )– day 93

Nothing to fear

种一棵树最好的时间是十年前，其次是现在！

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.7.5

人一我十，人十我百，追逐青春的梦想，怀着自信的心，永不言弃！

GPLT - L2-017 人以群分

排序 + 贪心

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100005;
int a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n ;i ++)
    {
        cin >> a[i];
    }   
    sort(a , a + n);
    int k = n >> 1 , out = 0, intro = 0;
    for(int i = 0;i < n;i ++)
    {
        if(i < k)intro += a[i];
        else out += a[i];
    }
    printf("Outgoing #: %d\n", n - k);
    printf("Introverted #: %d\n", k);
    printf("Diff = %d\n", abs(out - intro));
    return 0;
}

GPLT - L2 - 019 悄悄关注

考点 ： hash , map , unordered_map , 排序

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <unordered_map>
#include <algorithm>
#include <vector>

using namespace std;

int n , m;
struct node{
    string name;
    int val;
};

unordered_map<string , bool> ma;
vector<string> ans;
int main()
{
    cin >> n;
    string s;
    for(int i = 0;i < n;i ++)
    {
        cin >> s;
        ma[s] = true;
    }
    cin >> m;
    vector<node> v;
    int time = 0 , avg = 0;
    for(int i = 0;i < m;i ++)
    {
        cin >> s >> time;
        v.push_back({s , time});
        avg += time;
    }
    avg = avg / m;
    for(int i = 0;i < m;i ++)
    {
        if(v[i].val > avg)
        {
            if(!ma[v[i].name])
            {
                ans.push_back(v[i].name);
            }
        }
    }
    if(ans.size() == 0)
    {
        printf("Bing Mei You\n");
    }else{
        sort(ans.begin(), ans.end());
        for(int i = 0;i < ans.size() ;i ++)
        {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

1371C - A Cookie for You

分析

首先 n + m <= a + b 必须满足因为不满足这个条件，则一定会有客人无法吃到饼干，一定会失败

其次，当type2的客人来的时候或者 ，a == b的时候，min(a , b) 会减少 1.

所以我们需要考虑：所有type2类型的客人先来，然后type1类型的客人后来。如果有type1类型的客人比type2类型的客人先到，最好交换他们，因为如果类型2来宾之前有类型1来宾，则类型1来宾就有可能不必要地减小min（a，b）min（a，b）的值。）最后，当至少有一个cookie（两种类型都可以）时，所有1类客人都吃一个cookie。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
    ll a , b , n , m , k;
    cin >> a >> b >> n >> m;
    if(a > b){
        swap(a , b);
    }
    if(a < m)
    {
        printf("NO\n");
        return;
    }
    if(a + b < n + m)
    {
        printf("NO\n");
        return;
    }else printf("YES\n");
}
int main()
{
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed; // 在iomanip中
#endif
    SIS;
    cin >> t;
    while(t--)
    {
        slove();
    }
#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}