头像

魔法学徒




离线:17小时前


最近来访(46)
用户头像
Toduring
用户头像
历险少年
用户头像
jieHeEternity
用户头像
狗tt
用户头像
大雪莱
用户头像
半瓶可乐
用户头像
轩鹤.⁶
用户头像
断然
用户头像
青春猪头少年不会梦到AC
用户头像
wssdl
用户头像
xiuzhiyuan
用户头像
AcWing2AK
用户头像
窗外的麻雀
用户头像
陆修远
用户头像
冰之韵
用户头像
灰原哀
用户头像
北边小洛
用户头像
番红柿要吃西茄
用户头像
ZagY
用户头像
心里没有一点AC数

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

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e4+10;

int n;
int res = -2e9;
int sum;
struct Cow 
{
    int w, s;
    bool operator<(const Cow& C)const
    {
        return w+s<C.w+C.s;// 按w+s从小到大把牛排序
    }
} cows[N];

int main() 
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d%d",&cows[i].w,&cows[i].s);
    sort(cows, cows+n);
    for (int i = 0; i < n; i++) 
    {
      res = max(res, sum - cows[i].s);
      sum += cows[i].w; // 当只有一头牛时危险系数为-s
    }
    printf("%d\n",res);
}



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

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;

int n;
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    sort(q, q + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);

    printf("%d\n", res);
    return 0;
}


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

/*
t1,t2,t3,......,tn 后面n-1个人都得等t1时间,n-2个人都得t2时间......
t1*(n-1) + t2*(n-2) + ... +t(n-1)*(1)
*/
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
int n;
int a[N];
ll ans;

int main()
{
    scanf("%d",&n);
    for (int i = 0; i <=n; i++) 
        scanf("%d",&a[i]);

    sort(a , a+n);

    for (int i = 0; i <n; i++) 
        ans += a[i] * (n-i-1);

    printf("%lld\n",ans);
    return 0;
}


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

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
// 哈弗曼树,每次合并重量最小的两堆果子
int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", res);
    return 0;
}



题目描述

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。

输出最少区间数,如果无法完全覆盖则输出 −1。

输入格式
第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。

第二行包含整数 N,表示给定区间数。

接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需最少区间数。

如果无解,则输出 −1。

数据范围
1≤N≤105,
−10^9≤ai≤bi≤10^9,
−10^9≤s≤t≤10^9

输入样例

1 5
3
-1 3
2 4
3 5

输出样例

2

算法步骤
1.将所有区间按照左端点从小到大排序
2.从前往后依次枚举各区间,在所能覆盖指定区间的区间中,找到右端点最靠右的那个,然后将st更新为右端点的值

#include <iostream>
#include <algorithm>
using namespace std;

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

int main()
{
    int st, ed;// 指定线段的两个端点左st右ed
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &range[i].l, &range[i].r);
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)// 在所有左端点在st之前的区间中找
        {
            r = max(r, range[j].r);// 找右端点最靠右的那一个
            j ++ ;                 // 记录这是找到第几个区间了
        }

        if (r < st)                // 如果这些区间连最右端点都在st左边
        {
            res = -1;              // 就省省力气break掉,不可能拼成
            break;
        }
                                   // 如果最右端点在st右边,说明有戏,继续往下拼
        res ++ ;                   // 记下这个最右端点所在的区间,把它的右端点设为新的st
        if (r >= ed)               // 往下拼之前先等一等,若刚才那个右端点比指定线段的ed还右
        {                                
            success = true;        // 那就已经直接拼成了,不用继续往下拼了
            break;
        }

        st = r;                    // 刚才提到右端点设为新st
        i = j - 1;                 // 刚才记录第几个区间的时候,找最右找到头,多算了一个,这里减回来
    }

    if (!success) res = -1;        // 没拼成res记为-1,拼成res记为用了几个区间
    printf("%d\n", res);

    return 0;
}


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

#include <iostream>
#include <algorithm>
using namespace std;

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

int main()
{
    int st, ed;// 指定线段的两个端点左st右ed
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &range[i].l, &range[i].r);
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)// 在所有左端点在st之前的区间中找
        {
            r = max(r, range[j].r);      // 找右端点最靠右的那一个
            j ++ ;                       // 记录这是找到第几个区间了
        }

        if (r < st)                      // 如果这些区间连最右端点都在st左边
        {
            res = -1;                    // 就省省力气break掉,不可能拼成
            break;
        }
                                         // 如果最右端点在st右边,说明有戏,继续往下拼
        res ++ ;                         // 记下这个最右端点所在的区间,把它的右端点设为新的st
        if (r >= ed)                     // 往下拼之前先等一等,若刚才那个右端点比指定线段的ed还右
        {                                
            success = true;              // 那就已经直接拼成了,不用继续往下拼了
            break;
        }

        st = r;                          // 刚才提到右端点设为新st
        i = j - 1;                       // 刚才记录第几个区间的时候,找最右找到头,多算了一个,这里减回来
    }

    if (!success) res = -1;              // 没拼成res记为-1,拼成res记录用了几个区间
    printf("%d\n", res);

    return 0;
}


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

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

using namespace std;
const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l; // 左区间从小到大排序
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &range[i].l, &range[i].r);
    }

    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int>> heap;// 小顶堆

    for (int i = 0; i < n; i ++ )//从前往后枚举每个区间,判断此区间能否将其放到现有的组中
    {
    // 当前区间的左端点比现有组中最小的右端点还小,放到任何一组都会有相交部分
        if (heap.empty() || heap.top() >= range[i].l){
            heap.push(range[i].r);// 不可合并,只能新开一组
        }
        else {                    // 可以合并
            heap.pop();
            heap.push(range[i].r);// 更新合并后的区间右端点位置
        }
    }
    printf("%d\n", heap.size());
    return 0;
}

方法二来自 神仙解法

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100100;

int n;
int b[2 * N], idx;

int main()
{
    scanf ("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;
        b[idx ++] = r * 2 + 1;
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for(int i = 0; i < idx; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;

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

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++)
    {
        if(ed<range[i].l)
        {
            res++;
            ed=range[i].r;
        }
    }
    printf("%d",res);
    return 0;
}



题目描述

给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 N,表示区间数。

接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需的点的最小数量。

数据范围
1≤N≤105,
−109≤ai≤bi≤109

输入样例

3
-1 1
2 4
3 5

输出样例

2

题意:使用尽可能少的点覆盖几个区间

算法思想:贪心,每次都选择当前状态下的局部最优解,最后往往也收获全局最优解.

思想演绎:如何找局部最优解?即思考有两个区间的时候如何选最少的点覆盖这两个区间.可以分情况讨论
当两区间无交集时,最少需要两个点,有交集时最少只需一个点,当两区间明明有交集,却不慎选了个不在交集中的点,那一个点也不够.所以两个区间的最优解就是先把第一个区间的右端点选上,第二个区间覆盖了就不用选了,没覆盖再选第二个区间右端点.
如何把2个区间局部最优解推演到n个区间全局最优解?依样画葫芦,把n个区间按右端点从小到大排序,先把第一个区间右端点选上,遍历剩下的区间,每次都选没被之前点覆盖的区间的右端点.这些点的个数即最小值.
贪心.png

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int n;
struct Range // 区间结构体
{
    int l, r;
    bool operator< (const Range &W)const 
    {
        return r < W.r;   // 重载<按区间右端点排序
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9; // 用ed存储上一个定好的点的位置
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;        // 只要当前区间无法覆盖上一个点的坐标就要选新的点了
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}


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

题意:使用尽可能少的点覆盖几个区间

算法思想:贪心,每次都选择当前状态下的局部最优解,最后往往也收获全局最优解.

思想演绎:如何找局部最优解?即思考有两个区间的时候如何选最少的点覆盖这两个区间.可以分情况讨论
当两区间无交集时,最少需要两个点,有交集时最少只需一个点,当两区间明明有交集,却不慎选了个不在交集中的点,那一个点也不够.所以两个区间的最优解就是先把第一个区间的右端点选上,第二个区间覆盖了就不用选了,没覆盖再选第二个区间右端点.
如何把2个区间局部最优解推演到n个区间全局最优解?依样画葫芦,把n个区间按右端点从小到大排序,先把第一个区间右端点选上,遍历剩下的区间,每次都选没被之前点覆盖的区间的右端点.这些点的个数即最小值.

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int n;
struct Range // 区间结构体
{
    int l, r;
    bool operator< (const Range &W)const 
    {
        return r < W.r;   // 重载<按区间右端点排序
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9; // 用ed存储上一个定好的点的位置
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;        // 只要当前区间无法覆盖上一个点的坐标就要选新的点了
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}