首页 > 其他分享 >P2949 【USACO09OPEN】 Work Scheduling G

P2949 【USACO09OPEN】 Work Scheduling G

时间:2024-11-10 22:09:27浏览次数:1  
标签:Node USACO09OPEN PII int sum Work mid Scheduling include

P2949 [USACO09OPEN] Work Scheduling G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

反悔贪心

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;

int n, m;
PII g[N];
priority_queue<PII, vector<PII>, greater<PII>> q;


int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        g[i] = {l, r};
    }
    
    sort(g + 1, g + 1 + n);
    
    LL ans = 0;
    for (int i = 1; i <= n; i ++ )
    {
        swap(g[i].x, g[i].y);
        if (g[i].y > q.size()) 
        {
            q.push(g[i]);
            ans += g[i].x;
        }
        else
        {
            auto t = q.top();
            if (t.x >= g[i].x) continue;
            q.pop();
            q.push(g[i]);
            ans -= t.x;
            ans += g[i].x;
        }
    }
    cout << ans << endl;
    
    return 0;
}

线段树上二分

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;

int n, m;
PII g[N];
int trs[N];
bool st[N];

struct Node 
{
    int l, r;
    int sum;
}tr[N * 4];

void pushup(Node &u, Node &l, Node &r)
{
    u = {l.l, r.r, l.sum + r.sum};
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int k)
{
    if (tr[u].l == tr[u].r) tr[u].sum = k;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, k);
        else modify(u << 1 | 1, x, k);
        pushup(u);
    }
}


int query(int u, int l, int r)
{
    if (tr[u].l == tr[u].r) 
    {
        if (tr[u].sum) return -1;
        return tr[u].l;
    }
    else if (l <= tr[u].l && tr[u].r <= r)
    {
        int ls = tr[u << 1 | 1].l, rs = tr[u << 1 | 1].r, len = rs - ls + 1; 
        if (tr[u << 1 | 1].sum < len) return query(u << 1 | 1, l, r);
        else return query(u << 1, l, r);
    }
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = -1;
        if (r > mid) res = query(u << 1 | 1, l, r);
        if (res == -1 && l <= mid) res = query(u << 1, l, r);
        return res;
    }
}

int query1(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1, sum = 0;
        if (r > mid) sum += query1(u << 1 | 1, l, r);
        if (l <= mid) sum += query1(u << 1, l, r);
        return sum;
    }
}

int main()
{
    cin >> n;
    int maxv = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a = min(a, 100010);
        g[i] = {b, a};
        maxv = max(a, maxv);
    }
    
    sort(g + 1, g + 1 + n);
    reverse(g + 1, g + 1 + n);
    
    build(1, 1, maxv);
    
    LL sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x = query(1, 1, g[i].y);
        // cout << x << endl;
        if (x != -1) 
        {
            modify(1, x, 1);
            // cout << x << endl;
            sum += g[i].x;
        }
    }
    cout << sum << endl;
    return 0;
    
}

树状数组 + 二分

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;

int n, m;
PII g[N];
int trs[N];

struct Node 
{
    int l, r;
    int sum;
}tr[N * 4];

bool cmp(PII a, PII b)
{
    return a.x > b.x;    
}

void pushup(Node &u, Node &l, Node &r)
{
    u = {l.l, r.r, l.sum + r.sum};
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int k)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].sum = k;
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, k);
        else modify(u << 1 | 1, x, k);
        pushup(u);
    }
}


int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1, sum = 0;
        if (l <= mid) sum += query(u << 1, l, r);
        if (r > mid) sum += query(u << 1 | 1, l, r);
        return sum;
    }
}

int find(int x)
{
    int l = 0, r = x;
    
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        
        if (query(1, max(1, mid), x) < x - mid + 1) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    cin >> n;
    int maxv = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a = min(a, (int)1e5);
        g[i] = {b, a};
        maxv = max(a, maxv);
    }
    
    sort(g + 1, g + 1 + n, cmp);
    build(1, 1, maxv);
    
    LL sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x = find(g[i].y);
        if (x) 
        {
            modify(1, x, 1);
            sum += g[i].x;
        }
    }
    
    
    
    cout << sum << endl;
    return 0;
    
}

标签:Node,USACO09OPEN,PII,int,sum,Work,mid,Scheduling,include
From: https://www.cnblogs.com/blind5883/p/18538634

相关文章

  • SchedulingConfigurer 实现定时任务(动态修改cron,解决@Scheduled需重启服务问题)
    通过实现SchedulingConfigurer接口,实现定时任务,解决@Scheduled的定时任务改动cron需要服务重启的问题。@Slf4j@ComponentpublicclassATestScheduleJobimplementsSchedulingConfigurer{@Value("${a.c:0/5****?}")privateStringcron1;@Override......
  • LitServe 服务多worker启动简单说明
    LitServe是一个基于fastapi包装的快速推理api服务,以下只简单说明下关于server启动部分的处理参考使用我们可以通过配置devices以及每个device对应的worker数执行以那种模式进行server的启动(多线程还是多进程)参考使用if__name__=="__main__":#EnabletheOp......
  • Vmware Workstation Pro出现不可恢复错误:NOT_IMPLEMENTED bora\lib\unicode\unicod
    该问题今天被我碰到了,百度搜索无果后在Google搜到了官方community也有国人抱怨这个问题,他指出17.6.1版本经常碰到这个问题,于是我一路退回退回到17.5.2版本就好了,估计这是新版本的bug。这个bug和一个utf8编码的库出现错误有关。参见:https://community.broadcom.com/vmware-cloud-f......
  • SCC.369 Working with GPIO Moodle
    SCC.369Coursework1:WorkingwithGPIO Moodlesubmission16:00Fridayweek4;weighting33%ofmodule.AimHavingfamiliarizedyourselfwiththeCdevelopmentenvironmentandthebasicprocessofwritingtoregisterstocontroltheGPIOpins,inthiscour......
  • Neural Networks for Image  Classification Duration
    Lab2:NeuralNetworksforImage ClassificationDuration:2hoursTools:JupyterNotebookIDE:PyCharm==2024.2.3(oranyIDEofyourchoice)Python:3.12Libraries:oPyTorch==2.4.0oTorchVision==0.19.0oMatplotlib==3.9.2LearningObjectives:Unders......
  • 【Linux】为终端命令自定义快件键并弹窗提醒 设置快捷键切换网络代理(Network Proxy)Dis
    【Linux】为终端命令自定义快件键并弹窗提醒设置快捷键切换网络代理(NetworkProxy)Disabled/Manual并弹窗提醒可以自定义快捷键执行终端命令,执行完毕会有弹窗提醒。下面给一个例子,设置快捷键切换网络代理(NetworkProxy)Disabled/Manual并弹窗提醒。适用于Ubuntu系统,为......
  • spring6初体验(一、新建spring framework工程)
     初学spring6,最重要的是新建一个项目。本次工程使用IDEA2024编译器软件,同过maven进行构建。此博客可以创建多个spring项目(重复三过程),是多项目的创建方式一、准备一个空项目。二、为项目设置SDK点击文件选择项目设置,设置你的SDK 三、正式创建spring61.选择新建......
  • HyperWorks实体网格划分
    实体网格剖分在HyperMesh中,使用SolidMap功能进行实体网格剖分。该面板如下图所示:图4-4SolidMap面板 Ø通过SolidMapPanel进行实体网格剖分:•通过主菜单栏选择3D页面>solidmap。•通过下拉式菜单选择Mesh>create>SolidMap。 ØSolidMap......
  • VS 2022 不支持 .NET Framework 4.5 项目解决办法(Visual Studio 2022)
    VS2022不支持.NETFramework4.5项目解决办法(VisualStudio2022) 概述最近C#开发工具VisualStudio升级到了2022,打开速度快了很多,开发体验也舒服很多。只是使用过程中遇到了一个比较尴尬的问题:默认VisualStudio2022不再支持安装.NETFramework4.5组件,如下图所......
  • 阿里DataWorks注册UDTF函数
    1.背景    最近有个需求需要解析mongodb里面的json数据,采用的开发平台是dataworks,原始json内容如下:{"id":0,//方案ID"premiseDetails":[{"premiseId":0,//楼盘ID"price":0,//价格"pointDetails":[......