头像

ITNXD


访客:3203

离线:22小时前



ITNXD
5天前

简单注释

一个问题:按照如下证明得到的结果成了分情况讨论,也没有得到到底为啥排序后最优的结果。。。哪位小伙伴清楚可以给俺指点一二!

参考代码:

// 与"国王游戏"一样

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10;

int n;
PII cow[N];

// 按照s + w从小到大排序
// 证明:假设最终答案不是按照s + w从小大大排序的,则一定存在逆序对 w[i] + s[i] > w[i + 1] + s[i + 1]
// 考虑变化前后i位置和i + 1位置的牛 
//                  i位置                               i + 1位置
// 交换后  w[0]+w[1]+...+w[i-1]+w[i+1]-s[i]      w[0]+w[1]+...+w[i-1]-s[i+1]
// 交换前  w[0]+w[1]+...+w[i-1]-s[i]             w[0]+w[1]+...+w[i-1]+w[i]-s[i+1]

// 公共部分去掉
// w[i+1]-s[i]      -s[i+1]
// -s[i]            w[i]-s[i+1]

// 同时加s[i]+s[i+1]得
// w[i+1]+s[i+1]        s[i]
// s[i+1]               w[i]+s[i]

// 由于都是正数 交换前最大值为w[i]+s[i]
// 由基础条件知道 w[i]+s[i] > w[i+1]+s[i+1] 且 w[i]+s[i] > s[i],所以如果存在逆序对,则交换后更优 没有逆序对则交换前更优
// 证明也是不是很符合逻辑。。。成了分情况讨论了

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int w, s;
        cin >> w >> s;
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for(int i = 0; i < n; i++){
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

ITNXD
5天前
// 与"国王游戏"一样

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10;

int n;
PII cow[N];

// 按照s + w从小到大排序
// 证明:假设最终答案不是按照s + w从小大大排序的,则一定存在逆序对 w[i] + s[i] > w[i + 1] + s[i + 1]
// 考虑变化前后i位置和i + 1位置的牛 
//                  i位置                               i + 1位置
// 交换后  w[0]+w[1]+...+w[i-1]+w[i+1]-s[i]      w[0]+w[1]+...+w[i-1]-s[i+1]
// 交换前  w[0]+w[1]+...+w[i-1]-s[i]             w[0]+w[1]+...+w[i-1]+w[i]-s[i+1]

// 公共部分去掉
// w[i+1]-s[i]      -s[i+1]
// -s[i]            w[i]-s[i+1]

// 同时加s[i]+s[i+1]得
// w[i+1]+s[i+1]        s[i]
// s[i+1]               w[i]+s[i]

// 由于都是正数 交换前最大值为w[i]+s[i]
// 由基础条件知道 w[i]+s[i] > w[i+1]+s[i+1] 且 w[i]+s[i] > s[i],所以如果存在逆序对,则交换后更优 没有逆序对则交换前更优
// 证明也是不是很符合逻辑。。。成了分情况讨论了

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int w, s;
        cin >> w >> s;
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for(int i = 0; i < n; i++){
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

ITNXD
6天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, a[N];

// 绝对值不等式
// 设n家店为:x1 x2 x3 ... xn   货仓为 x
// 答案 = |x1 - x| + |x2 - x| + ... |xn - x|
// 首尾组合得:(|x1 - x| + |xn - x|) + (|x2 - x| + |xn - 1 - x|) + ...
// 只看第一组,会发现只要x处于x1和xn之间,结果为最小是xn - x1,同理对于后面的所有组只要取到每一组的中间即可得到最优解
// 即只要取到所有数的中位数的位置即可保证该解最优,即改点在每个组内部

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int res = 0;
    for(int i = 0; i < n / 2; i++) res += abs(a[i] - a[n - i - 1]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

ITNXD
6天前
#include <iostream>
#include <algorithm>

using namespace std;

const int  N = 1e5 + 10;

int n, a[N];
long long res;

// 会发现后面的人要等前面的所有人打完才可以打水,所以对于所有人来说:
// a[0] 需要被后面人等待n - 1次
// a[1] n - 2
// ...
// a[n - 1] 0

// 从小到大排序即可

// 证明就很简单了:权重大的用小的上得到的一定是最优值,可以通过调整法,反证法交换证明,由于很容易想到该做法正确性就不做证明了

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for(int i = 0; i < n; i++) res += a[i] * (n - i - 1);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

ITNXD
6天前
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;

// 每次合并最小的两堆即可
// 本质就是哈夫曼树,根节点为所有果子,为一颗完全二叉树,若有儿子,则儿子一定是两个
// 每个儿子加的次数是由到根节点距离决定的!

// 证明:选择最小的两个点,一定是哈夫曼树最深(同一层)的两个点,且最优
// 反证:三个点,a为最深 b为最深 c不是最深 且b不是最小点,而c是最小点(即最小的两个点不一定全为最深)
// 则:会发现b和c交换会使得代价更小,即最小的两点一定是最深且结果最优
// 具体数学证明可以画图用字母表示一下即可!
// 本题的局部最优解是可以走到全局最优解的,对于第一步的选择是最优,剩下的n - 1个果子的选择的最终代价都包含第一步的代价,则可以先去掉第一步,则问题转化为球n - 1个果子的最优值,则会发现局部最优解可以到达全局最优解

int main(){
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        heap.push(x);
    }
    int res = 0;
    while(heap.size() > 1){
        auto a = heap.top(); heap.pop();
        auto b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    cout << res << endl;
    return 0;
}



ITNXD
7天前

简单题解

参考代码:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int n, st, ed;

struct Range{
    int l, r;
    bool operator < (const Range w) const {
        return l < w.l;
    }
}range[N];

// 1. 按照区间左端点排序
// 2. 从前向后扫描所有能覆盖目标区间左端点start的区间中,选择右端点最大的区间,并更新目标区间的左端点为最大右端点

// 简单证明:对于res(最终答案:每个区间右端点不一定最大) 和 cnt(我们算法的答案)
// 对于res会发现他会被cnt的每个区间覆盖掉,可以证明最终res = cnt

int main(){
    cin >> st >> ed >> n;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n);

    int res = 0;
    // sucess用来判断最后一部分能否完全覆盖,不可省略
    bool sucess = false;
    for(int i = 0; i < n;){
        int j = i, r = -2e9;
        // j = i 表示从第一个没有扫描的区间开始
        // 将所有包含目标区间开始位置的区间的最大右端点找出来,其他不是最大的就是没用的区间
        while(j < n && range[j].l <= st){
            r = max(r, range[j].r);
            j ++;
        }
        // 最大右端点都到不了区间开始则输出-1结束
        if(r < st){
            cout << -1 << endl;
            return 0;
        }
        res ++;
        // 当前最大右端点比目标区间都长,提前结束
        if(r >= ed){
            sucess = true;
            break;
        }
        // 更新目标区间开始位置为当前最大右端点,扫描位置更新为j,即没有扫描过的第一个位置
        st = r, i = j;
    }
    if(sucess) cout << res << endl;
    else cout << -1 << endl;
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

ITNXD
7天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int n, st, ed;

struct Range{
    int l, r;
    bool operator < (const Range w) const {
        return l < w.l;
    }
}range[N];

// 1. 按照区间左端点排序
// 2. 从前向后扫描所有能覆盖目标区间左端点start的区间中,选择右端点最大的区间,并更新目标区间的左端点为最大右端点

// 简单证明:对于res(最终答案:每个区间右端点不一定最大) 和 cnt(我们算法的答案)
// 对于res会发现他会被cnt的每个区间覆盖掉,可以证明最终res = cnt

int main(){
    cin >> st >> ed >> n;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n);

    int res = 0;
    // sucess用来判断最后一部分能否完全覆盖,不可省略
    bool sucess = false;
    for(int i = 0; i < n;){
        int j = i, r = -2e9;
        // j = i 表示从第一个没有扫描的区间开始
        // 将所有包含目标区间开始位置的区间的最大右端点找出来,其他不是最大的就是没用的区间
        while(j < n && range[j].l <= st){
            r = max(r, range[j].r);
            j ++;
        }
        // 最大右端点都到不了区间开始则输出-1结束
        if(r < st){
            cout << -1 << endl;
            return 0;
        }
        res ++;
        // 当前最大右端点比目标区间都长,提前结束
        if(r >= ed){
            sucess = true;
            break;
        }
        // 更新目标区间开始位置为当前最大右端点,扫描位置更新为j,即没有扫描过的第一个位置
        st = r, i = j;
    }
    if(sucess) cout << res << endl;
    else cout << -1 << endl;
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

ITNXD
7天前
// 111题

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int n;

struct Range{
    int l, r;
    bool operator < (const Range & w) const {
        return l < w.l;
    }
}range[N];

// 1. 按照区间左端点排序
// 2. 从小到大扫描所有区间
//      2.1 若当前组无法合并入已有组则新建一个组
//      2.2 否则,将当前组合并,更新当前组的mar_r

// 证明:res <= cnt res >= cnt
// 1. res <= cnt 首先cnt是一种合法方案,答案求得是最小组数,所以res <= cnt
// 2. res >= cnt 前cnt - 1个组的左端点一定小于当前区间左端(区间按照左端点排序),并且当前区间右端点一定小于所有组的右端点,即cnt个组一定有交集,所以答案一定大于cnt 即 res >= cnt
// 因此得证:res = cnt

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }

    sort(range, range + n);
    // 保存每个组的最大右端点max_r
    priority_queue<int, vector<int>, greater<int>> heap;

    for(int i = 0; i < n; i++){
        auto t = range[i];
        // 堆空或当前区间无法合并到已有组则开新组(当前区间左端点在所有组中的最小max_r之前)
        if(heap.empty() || t.l <= heap.top()) heap.push(t.r);
        // 否则更新当前最小组的右端点为当前区间的右端点
        else heap.pop(), heap.push(t.r);
    }
    // 堆大小就是区间的组数
    cout << heap.size() << endl;
    return 0;
}



ITNXD
8天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int n;

// 1. 按照区间右端点排序
// 2. 扫描每一个区间
// 2.1 若当前区间已被选过点直接跳过
// 2.2 否则,选择当前区间作为该区间

// 贪心:以右端点排序,当每个区间独立时,选择当前区间时为最优,简单解释,后面的区间的左端点可能比当前区间右端点靠前或靠后,但选择当前区间右端点,则重复区间就会被过滤掉
// 按照夹逼定理来证明 res 为最终答案 cnt 为我们按照当前贪心思路算出来的答案
// 1. res <= cnt  反证法:没太听明白。。。
// 2. res >= cnt  若想选区间则一定是贪心的2.1的情况,则说明选区间的情况为区间之间两两不重合的区间,并且我们选择当前区间,不相交,则要将每个区间都选一次,由于res为最大区间数,cnt可能不是最优解,即res >= cnt
// 因此得证:res = cnt

struct Range{
    int l, r;
    bool operator < (const Range & w){
        return r < w.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
        if(range[i].l > ed)
            res ++, ed = range[i].r;

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

ITNXD
8天前

112题用到该知识

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int n;

// 1. 按照区间右端点排序
// 2. 扫描每一个区间
// 2.1 若当前区间已被选过点直接跳过
// 2.2 否则,选择当前区间右端点作为该点

// 贪心:以右端点排序,选择每个区间的右端点时为最优,简单解释,后面的区间的左端点可能比当前区间右端点靠前或靠后,但选择当前区间右端点会最大限度的接近后面区间,为最优值
// 按照夹逼定理来证明 res 为最终答案 cnt 为我们按照当前贪心思路算出来的答案
// 1. res <= cnt  很明显,若我们得到的答案可能不是最优解,则最终答案res要小于等于cnt
// 2. res >= cnt  若想选点则一定是贪心的2.1的情况,则说明选点的情况为区间之间两两不重合的区间,并且我们选择每个区间的右端点,若要将每个区间覆盖则至少需要cnt个点,即res >= cnt
// 因此得证:res = cnt

struct Range{
    int l, r;
    bool operator < (const Range & w){
        return r < w.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
        if(range[i].l > ed)
            res ++, ed = range[i].r;

    cout << res << endl;
    return 0;
}