Skip to content

14048: 【原4048】Evensgn的坚定之桌

题目

题目描述

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

题目描述

Evensgn

这张桌子一共有 \(n\) 条腿，第 \(i\) 条腿的长度为 \(l_i\)。

Evensgn 决定拆除这张桌子的一些桌腿来使它变得稳定。对于每条桌腿，Evensgn 已经预判出了 \(d_i\) ——拆除第 \(i\) 条桌腿所需要花费的时间。

众所周知，有这样一句古老的谚语，“一张有 \(k\) 条腿的桌子被称作是 稳定的，当且仅当它有 多于一半数量 的桌腿是最大长度的。”

例如，如果一张有 \(5\) 条桌腿的桌子是稳定的，那么它的 \(5\) 条桌腿中至少有 \(3\) 条桌腿是最大长度的。又例如，一张只有 \(1\) 条桌腿的桌子总是稳定的，而一张有 \(2\) 条桌腿的桌子是稳定的当且仅当这两条桌腿是相同长度的。

Evensgn 想要留出时间看 《逃避虽可耻但有用》 里的 gakki ，因此他希望在最少的时间内将这张桌子变成 稳定的。他找到了你，请你帮忙计算他所需要花费的最少时间是多少。

输入格式

  • 第一行为一个整数 \(n\) ，表示 Evensgn 的新桌原先的桌腿数量。
  • 接下来一行为 \(n\) 个整数 \(l_i\)，\(l_i\) 表示第 \(i\) 条桌腿的长度。
  • 接下来一行为 \(n\) 个整数 \(d_i\)，\(d_i\) 表示 Evensgn 拆除第 \(i\) 条桌腿所需要花费的时间。

输出格式

输出一个整数，Evensgn 将新桌变成 稳定的 所需要花费的最少时间。

输入输出样例

不知为何，这道题目的样例数量竟然达到了惊人的 \(3\) 组。

样例输入1

2
1 5
3 2

样例输出1

2

样例输入2

3
2 4 4
1 1 1

样例输出2

0

样例输入3

6
2 2 1 1 3 3
4 3 5 5 2 1

样例输出3

8

数据规模

  • 对于 \(30\%\) 的数据，\(1 \leq n \leq 100, 1 \leq l_i \leq 10^5, 1 \leq d_i \leq 200\)。
  • 对于 \(70\%\) 的数据，\(1 \leq n \leq 1000, 1 \leq l_i \leq 10^5, 1 \leq d_i \leq 200\)。
  • 对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5, 1 \leq l_i \leq 10^5, 1 \leq d_i \leq 200\)。

FineArtz's solution 

/* Evensgn的坚定之桌 */
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

class Leg{
public:
    int d = 0, l = 0;
};
bool cmp(Leg l1, Leg l2){
    return (l1.l < l2.l || (l1.l == l2.l && l1.d < l2.d));
}
/*bool cmp2(Leg l1, Leg l2){
    return (l1.d < l2.d);
}*/

Leg leg[100005];
int f[100005], d[205];
int n;

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> leg[i].l;
    for (int i = 1; i <= n; ++i)
        cin >> leg[i].d;
    sort(leg + 1, leg + n + 1, cmp);
    f[1] = 0;
    int nowl = 1;
    for (int i = 2; i <= n; ++i){
        if (leg[i].l == leg[i - 1].l) ++nowl;
        else{
            for (int k = i - 1; k >= i - nowl; --k)
                ++d[leg[k].d];
            nowl = 1;
        }
        if (nowl > i / 2) f[i] = 0;
        else{
            int tmp1 = f[i - 1] + leg[i].d;
            int tmp2 = 0, cnt = 0, lim = i - 2 * nowl + 1;
            for (int k = 0; k <= 200; ++k){
                if (cnt + d[k] >= lim){
                    tmp2 += k * (lim - cnt);
                    break;
                }
                else{
                    tmp2 += k * d[k];
                    cnt += d[k];
                }
            }
            f[i] = min(tmp1, tmp2);
        }
    }
    cout << f[n] << endl;
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
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;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //反向迭代器
    template <class U>
    class reverse_iterator {
        U val;
        friend reverse_iterator<U> mVector<T>::rbegin();
        friend reverse_iterator<U> mVector<T>::rend();
    public:
        U& base() {
            return val;
        }
        reverse_iterator() = default;
        reverse_iterator(const reverse_iterator<U>& other) {
            val = other.val;
        }
        reverse_iterator(const U& other) {
            val = other;
        }
        reverse_iterator<U>& operator++() {
            --val;
            return *this;
        }
        reverse_iterator<U> operator++(int) {
            reverse_iterator<U> temp(*this);
            --val;
            return temp;
        }
        reverse_iterator<U>& operator--() {
            ++val;
            return *this;
        }
        reverse_iterator<U> operator--(int) {
            reverse_iterator<U> temp(*this);
            ++val;
            return temp;
        }
        bool operator==(const reverse_iterator<U>& other) const {
            return val == other.val;
        }
        bool operator!=(const reverse_iterator<U>& other) const {
            return val != other.val;
        }
        reverse_iterator<U>& operator=(const reverse_iterator<U>& other) {
            val = other.val;
            return *this;
        }
        T& operator*() const {
            return *val;
        }
    };

    reverse_iterator<iterator> rbegin() {
        auto temp = end();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    reverse_iterator<iterator> rend() {
        auto temp = begin();
        --temp;
        reverse_iterator<iterator> result;
        result.val = temp;
        return result;
    }

    //增加元素
    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;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    size_t get_size() {
        return size;
    }

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

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

class leg {
public:
    int length = 0,
        times = 0;
};

leg table[100009];
int houzhui[100009] = { 0 };
int time_sum[209] = { 0 };

mVector<int> length_sum[100009];

int main() {
    int n;
    int max_length = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i)
        scanf("%d", &table[i].length);
    for (int i = 0; i < n; ++i)
        scanf("%d", &table[i].times);

    for (int i = 0; i < n; ++i) {
        length_sum[table[i].length].push_back(table[i].times);
        max_length = table[i].length > max_length ? table[i].length : max_length;
    }

    //计算后缀和
    for (int i = 100005; i >= 0; --i) {
        houzhui[i] = houzhui[i + 1];
        for (int j = 0; j < length_sum[i].get_size(); ++j)
            houzhui[i] += length_sum[i][j];
    }

    int ans = int(1e9 + 7);
    //遍历计算
    for (int i = 1, cur_remain = 0; i <= max_length; ++i) {
        if (length_sum[i].get_size() == 0)
            continue;
        int temp = houzhui[i + 1];
        //计算桶内的剩余
        for (int remain = cur_remain, pos = 0, step = 0; 
            remain >= length_sum[i].get_size(); --remain) {
            if (time_sum[pos] <= step) {
                for (++pos; time_sum[pos] == 0; ++pos);
                step = 0;
            }
            temp += pos;
            ++step;
        }
        ans = temp < ans ? temp : ans;
        //将当前长度入桶
        for (int j=0;j<length_sum[i].get_size();++j)
            ++time_sum[length_sum[i][j]];
        cur_remain += length_sum[i].get_size();
    }

    cout << ans;

    return 0;
}