11037: 【原1037】二哥买草

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1037

Description

二哥在网上买干草。他发现了一笔特殊的买卖。他每买一捆大小为A(1 <= A <= 1,000,000)的干草，他就能免费获得一捆大小为B(1 <= B < A)的干草,也就是说免费的那个必须大小是小于购买的那个。

然而，这笔交易是有规定的：大的一捆干草必须是高质量的，小的一捆是低质量的。二哥是个吝啬鬼，他并不在意：随便什么质量，只要能省钱就好。

给出一组N(1 <= N <= 10,000)捆高质量干草的大小，M(1 <= M <= 10,000)捆低质量的干草的大小，找出二哥最多能买多少捆干草。他能买高质量的干草，但他不能买低质量的干草（就是说，他只能通过赠送来获得低质量的草）。

Input Format

第一行给出N,M

下面N+M行，先给出高质量的N捆高质量干草的大小，再给出M捆低质量的

Output Format

二哥最多可以得到多少捆干草

Hint

对于面样例，二哥可以这样进行操作，买6得3，买3得1,买1时，不能拿到低质量的干草，最终得到5捆.

Sample Input

3 4
6
1
3
1
5
3
4

Sample Output

5

FineArtz's solution

/* 二哥买草 */
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int x, int y){
    return x > y;
}

int main(){
    int m, n;
    int a[10005], b[10005];
    cin >> n >> m;
    for (int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i){
        cin >> b[i];
    }
    sort(a, a + n, cmp);
    sort(b, b + m, cmp);
    int ans = n, j = 0;
    for (int i = 0; i < n; ++i){
        while (j < m && a[i] <= b[j])
            ++j;
        if (j == m)
            break;
        ++ans;
        ++j;
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[size];
        vector_data[size--] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

};

template <class T>
class myPriorityQueue {
    mVector<T> queueData;
    unsigned int sizeOfQueue = 0;
    bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

    //向下过滤
    void percolateDown(unsigned int pos) {
        while (pos * 2 <= sizeOfQueue) {
            if (pos * 2 + 1 > sizeOfQueue) {
                //交换
                if (cmp(queueData[pos * 2], queueData[pos])) {
                    auto temp = queueData[pos * 2];
                    queueData[pos * 2] = queueData[pos];
                    queueData[pos] = temp;
                }
                break;
            }
            else {
                bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
                if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
                    auto temp = queueData[pos * 2 + minNum];
                    queueData[pos * 2 + minNum] = queueData[pos];
                    queueData[pos] = temp;
                    pos = pos * 2 + minNum;
                }
                else break;
            }
        }
    }

public:
    //构建
    myPriorityQueue() {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //compare函数返回父结点a与孩子结点b的关系正确与否
    myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //根据数组建立堆
    void buildHeap(T* eleData, unsigned int eleNum) {
        queueData.clear();
        sizeOfQueue = eleNum;
        queueData.push_back(*new T);
        for (unsigned int i = 1; i <= eleNum; i++)
            queueData.push_back(eleData[i - 1]);
        //向下过滤
        for (unsigned int pos = eleNum / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    //判断是否空
    bool empty() {
        return sizeOfQueue == 0;
    }

    //返回队列大小
    auto size() {
        return sizeOfQueue;
    }

    //入队
    void push(const T & input) {
        sizeOfQueue++;
        queueData.push_back(input);

        //向上过滤
        for (auto i = sizeOfQueue; i > 1; i = i / 2) {
            //判断是否比父结点更小
            if (cmp(queueData[i], queueData[i / 2])) {
                //交换
                auto temp = queueData[i];
                queueData[i] = queueData[i / 2];
                queueData[i / 2] = temp;
            }
            else break;
        }
    }

    //队列最前
    T top() {
        return queueData[1];
    }

    //出队
    T pop() {
        auto temp = queueData[1];
        queueData[1] = queueData[sizeOfQueue--];
        queueData.pop_back();
        percolateDown(1);
        return temp;
    }
};
/*
int n_data[10009] = { 0 }, m_data[10009] = { 0 };
myPriorityQueue<int> n_queue([](int a, int b) {return a > b; }),
m_queue([](int a, int b) {return a > b; });

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; ++i)
        scanf("%d", &n_data[i]);
    for (int i = 0; i < M; ++i)
        scanf("%d", &m_data[i]);

    //建立堆
    n_queue.buildHeap(n_data, N);
    m_queue.buildHeap(m_data, M);

    long long ans = 0;
    for (; !n_queue.empty();) {
        auto temp = n_queue.pop();
        ++ans;
        for (; !m_queue.empty() && m_queue.top() >= temp; m_queue.pop());
        if (!m_queue.empty()) {
            m_queue.pop();
            ++ans;
        }
    }

    printf("%lld", ans);

    return 0;
}*/

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e4 + 100;
int good[maxN], bad[maxN];

void qSort(int *, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, ans = 0;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> good[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> bad[i];
    }
    qSort(good, 0, N - 1);
    qSort(bad, 0, M - 1);

    int g = 0, b = 0;
    while (g < N && b < M) {
        if (good[g] > bad[b]) {
            b++;
        }
        g++;
    }
    ans = N + b;
    cout << ans;

    return 0;
}

void qSort(int *nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    int key = nums[first];

    while (first < last) {
        while (first < last && nums[last] >= key) {
            --last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    qSort(nums, l, first - 1);
    qSort(nums, first + 1, h);
}

yyong119's solution

#include <iostream>
#include <algorithm>
 
int hq[10001], lq[10001];
int n, m, countl;
using namespace std;
 
int main(){
    cin>>n>>m;
    for (int i = 0; i < n; i++) cin>>hq[i];
    for (int i = 0; i < m; i++) cin>>lq[i];
    sort(hq, hq + n);
    sort(lq, lq + m);
    for (int i = 0; i < n; i++)
        if ((hq[i] > lq[countl])&&(countl < m)) countl++;
    cout<<n + countl<<endl;
}