夜雨聆风学习资料网

ARTICLE · 1377761

GESP 2024年12月 真题 运送物资 完整题解(贪心)

GESP 2024年12月 真题 运送物资 完整题解(贪心)
【GESP 2024年12月 真题 运送物资 完整题解(贪心)】
题目描述

小杨管理着 m 辆货车,每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点,这些站点位于 A 市和 B 市之间。

每次运送物资时,货车从初始运输站点出发,前往 A 市或 B 市,之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点,其中 A 市的坐标为 0,B 市的坐标为 x,运输站点的坐标为 p 且有 0 < p < x。货车每次去 A 市运送物资的总行驶路程为 2p,去 B 市运送物资的总行驶路程为 2(x - p)。

对于第 i 个运输站点,其位置为 pᵢ 且至多作为 cᵢ 辆车的初始运输站点。小杨想知道,在最优分配每辆货车的初始运输站点的情况下,所有货车每天的最短总行驶路程是多少。

样例
输入
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000
输出
40186
题解正文

先把结论摆前面:这题不难,但要一次写对,得按顺序来。

继续 GESP 2024年12月 真题。这道贪心题适合当模板练手——写对了,同一类题你都能照着套。

题目:运送物资
场次:2024年12月 六级|难度:六级
知识点:贪心 sort排序
链接:https://www.acgo.cn/problemset/info/75447

一、先看懂这道题

一句话概括:用贪心 sort排序把题目要求原样翻译成代码,属于考场上必须拿满分的题。

二、写之前先定三个前提

第一件,先注意数据范围。题干没直接写范围,但参考代码里用了 long long,说明中间结果会超过 21 亿——照抄类型就不会错。

第二件,再注意边界。题目说「到」或者「包括」,循环就是闭区间,<= 不能写成 <,否则漏掉最后一个数。

第三件,最后注意输出格式。把样例输出的每一行抄下来对着看,多了空格、少了换行都算错,这类失分最不值。

三、思路:跟着三个问题走

问题一:我手上有什么?样例第一行是 3 4 10,后面还有 7 行,用一个循环按行读进来最省事。变量名起得能看懂,后面改起来才不费劲。

问题二:要我交什么?别急着写算法,先把输出格式固定下来——这是全题最容易丢分的地方。

问题三:中间这一步怎么算?这是唯一需要动脑的地方。

m 辆货车,每个运输站 i 位置 pᵢ 最多停 cᵢ 辆。货车从站点去 A(坐标 0)再返回,路程 2p;去 B(坐标 x)再返回,路程 2(x-p)。每辆车可去 A 或去 B(次数给定?),要让总路程最短。把「去 A 节省/多花」与「去 B」比较:去 A 路程 2p,去 B 路程 2(x-p)。每辆车选较小的那个,同时受站点容量 cᵢ 约束。贪心:把站点按「去 A 更有利(p 小)」排序,优先分配去 A 的车到使路程最小的站点,剩余分配去 B。用排序 + 贪心选择。

先排序 → 读入数据 → 逐个处理(贪心的核心逻辑) → 按格式输出

结论:这题就是贪心的标准流程,不需要额外技巧。

四、完整代码

建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
ll x;
vector<pair<int,int> > st;
int a[N],b[N];
int main()
{
    cin>>n>>m>>x;  // 读入
    for(int i=1;i<=n;i++)  // 遍历
    {
        int p,c;
        cin>>p>>c;  // 读入
        st.push_back(make_pair(p,c));
    }
    sort(st.begin(),st.end());
    for(int i=1;i<=m;i++)  // 遍历
    {
        cin>>a[i]>>b[i];  // 读入
    }
    vector<pair<int,int> > neg,pos;
    ll res=0;
    for(int i=1;i<=m;i++)  // 遍历
    {
        if(a[i]>=b[i])  // 判断
        pos.push_back(make_pair(a[i]-b[i],i));
        else
        {
            neg.push_back(make_pair(a[i]-b[i],i));
        }
        res+=1ll*b[i]*x;
    }
    sort(neg.begin(),neg.end());
    sort(pos.begin(),pos.end());
    reverse(pos.begin(),pos.end());
    int l=0,r=n-1;
    for(auto i:neg)  // 遍历
    {
        while(r>=1&&st[r].second==0)r--;
        res+=1ll*(a[i.second]-b[i.second])*st[r].first;
        st[r].second-=1;
    }
    for(auto i:pos)  // 遍历
    {
        while(l<=n&&st[l].second==0)l++;
        res+=1ll*(a[i.second]-b[i.second])*st[l].first;
        st[l].second-=1;
    }
    cout<<res*2<<"\n";  // 输出
}
五、真正要动脑的只有这两段

逐段过一遍会太啰嗦,我只讲决定对错的那两段。

第一段,把数据读进来。

    cin>>n>>m>>x;

读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。

第二段,核心处理。

    for(int i=1;i<=m;i++)
    {
        if(a[i]>=b[i])
        pos.push_back(make_pair(a[i]-b[i],i));
        else
        {
            neg.push_back(make_pair(a[i]-b[i],i));
        }
        res+=1ll*b[i]*x;
    // …(这段后面还有,见上面的完整代码)

这段是整道题唯一需要想的地方,也是贪心的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。

六、拿样例验一遍

下面按四步验一遍,这个顺序建议你考试时也照做。

样例输入

3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000

样例输出

40186
步骤做什么通过标准
1拿样例对一遍输出和题目给的一模一样
2试最小的输入只给一个数、只给一行,程序不崩也不越界
3检查输出末尾没有多余空格,最后一行有换行
七、踩坑对照表

按危险程度从高到低排,第一条最常见:

  1. 排序方向写反——写成 sort(a, a+n) 想降序却用了默认升序 就错,应该是 降序要写 sort(a, a+n, greater<int>())。
  2. 累加结果溢出——写成 int sum = 0; 就错,应该是 long long 声明累加变量。
  3. 漏掉区间右端点——写成 i < R 就错,应该是 i <= R。
  4. 输出格式不符——写成 cout << ans; 就错,应该是 cout << ans << "\n";。
  5. 多组数据没清空——写成 全局数组直接用 就错,应该是 每组数据前 memset 或重新赋值。
八、收尾三行

这题的经验压缩成三行,考前扫一眼就够。

  • 这题考的:贪心 sort排序——把题目条件一句一句翻译成代码,不添不减。
  • 要记住的:每一步选当前最优,凭什么全局最优?想不出证明就先别用贪心,换成枚举或 DP 更稳。
  • 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。

下一篇继续同场次的真题。有更短的写法,欢迎评论区贴出来。


系列导航
  • 本文属于《GESP 真题题解》系列,第 75 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
  • 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
  • 想跟完整系列的朋友点个关注,更新会第一时间推送。
  • 本系列合集目录(按年份/组别排序)
写在最后

GESP 的坑多半在边界和读题上。这道贪心题把该注意的点都列在上面的表里了,提交前逐条过一遍。

今天想问你:这道题你第一次交是 WA 还是 AC?卡在哪一步,评论区说说,我帮你看看。

把这篇转给一起刷题的同学,两个人对着讲一遍思路,比一个人看三遍都管用。关注本号不迷路。

后台回复 “资料”,领历年真题完整代码包(持续更新)。

本篇编号 GESP-055(公众号 MP-055)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料