热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2016-2017ACM-ICPC东北欧区域赛(NEERC16)Gym101190E:离线查询与排序优化策略

题目链接:http://codeforces.com/gym/101190/attachments题意:在一个共享三轮车站点,某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说,需要设计一种算法,在满足所有用户需求的同时,最小化总等待时间和资源浪费。通过合理的数据结构和算法优化,可以显著提高系统的整体性能和用户体验。

题目链接:http://codeforces.com/gym/101190/attachments

题意:一个公共三轮车车站可以提供给一些人租车,但是在开始时刻,公园里有所少量车这个是不确定的,然后现在有n个信息和q个询问,信息有两种形式+ a b代表在a时间有b个人还车,另外一种是 - a b代表在a时间有b个人借车,这些人借车是要排队的,如果当前没有车,则只能等待,对于每一个询问给定了初始时刻车站里面有多少量车,然后要询问的是对于每一个可能的初始值的等待时间,如果等待时间是不确定的话,输出INFINITY。

解法&#xff1a;首先是一个单点更新的问题&#xff0c;可是我们发现一次更新之后会影响下一次的查询&#xff0c;或者你更新之后又可以回到之前的版本&#xff0c;所以可持久化&#xff1f;瞎几把yy之后&#xff0c;我们不妨来分析一下样例&#xff0c;可以观察到什么时候是要租车的呢&#xff1f;首先输入的信息用 op t[i] a[i]来表示一下&#xff0c;t[i]代表时间戳&#xff0c;a[i]代表人或者车的数量(取决于操作)&#xff0c;第二种操作意味着要减少a[i]量车&#xff0c;如果车你的数量减小到<&#61;0那么久只能等待了。并且当前要等待的时间是多少呢&#xff1f;我们容易把它预处理出来&#xff0c;下面的s[i]就是人或者车的数量的前缀和&#xff0c;显然为正代表当前时间不需要租车&#xff0c;否则需要租车。

for(int i &#61; 1; i <&#61; n; i&#43;&#43;){s[i] &#61; s[i-1] &#43; a[i];if(i 1] - t[i];}

处理出这个也不能解决这个问题&#xff0c;接下来显然当s[i]>0的那些时间段是不用考虑的&#xff0c;你想啊&#xff0c;当前车的数量够用&#xff0c;肯定傻子才会等待吧。所以我们把需要等待的总时间以及等待的时间段的长度记录下来

long long sum1 &#61; 0, sum2 &#61; 0;for(int i &#61; 1; i <&#61; n; i&#43;&#43;){if(s[i] <0){b[&#43;&#43;cnt] &#61; i;sum1 &#43;&#61; 1LL*(-s[i])*t[i];sum2 &#43;&#61; t[i];}}

接下来就是想到我们在线很难做那么我们可以离线做啊&#xff0c;所以就有了询问离线的思路了。我们会想离线该怎么做呢&#xff1f;容易想到我们会按照x来排序&#xff0c;离线是为了能用到之前处理的信息&#xff0c;而不是无序重来一遍&#xff0c;这样显然是可以降低复杂度的吧。所以我们会想到按照x从小到大排序&#xff0c;这里的x就是第初始的车的数量&#xff0c;想一下吧&#xff0c;当前x比较小的时候你覆盖了一些之前等待的时间区间&#xff0c;那么下次你的x比现在的大&#xff0c;也必然可以覆盖上次的区间&#xff0c;所以就不用重复扫描&#xff0c;自然大大降低了复杂度。

struct node{int x, id;bool operator <(const node &rhs) const{return x }c[maxn];

在询问离线的时候我已经提到了&#xff0c;要利用之前的信息&#xff0c;所以我们也要对那些需要等待的时间段进行排序&#xff0c;每一个时间段都有一个值代表当前等待的人数&#xff0c;这里是负数所以从大到小排&#xff0c;比如-2>-3&#xff0c;那么2会排在3的前面&#xff0c;那么你x增大&#xff0c;显然也是可以覆盖当前区间能覆盖的每一条线段的&#xff0c;然后我们按照这个思路去模拟一发就可以了。注意不确定的条件就是当当前的x&#43;s[n]<0的时候&#xff0c;这个时候显然车都不够。

sort(c &#43; 1, c &#43; q &#43; 1);for(int i &#61; 1; i <&#61; q; i&#43;&#43;){int x &#61; c[i].x;while(j <&#61; cnt && (-s[b[j]]) <&#61; x){sum1 -&#61; 1LL*(-s[b[j]]) * t[b[j]];sum2 -&#61; t[b[j]];&#43;&#43;j;}if(s[n] &#43; x <0){ans[c[i].id] &#61; -1;}else{ans[c[i].id] &#61; sum1 - x * sum2;}}

完整码&#xff1a;

#include
using namespace std;
const int maxn &#61; 1e5 &#43; 7;
int n, q;
int a[maxn], t[maxn];
int s[maxn];
int b[maxn], cnt;
long long ans[maxn];
struct node{int x, id;bool operator <(const node &rhs) const{return x }c[maxn];
bool cmp(int i, int j){return s[i] > s[j];
}int main()
{freopen("expect.in", "r", stdin);freopen("expect.out", "w", stdout);scanf("%d%d", &n, &q);for(int i &#61; 1; i <&#61; n; i&#43;&#43;){char op[5];scanf("%s%d%d", op, &t[i], &a[i]);if(op[0] &#61;&#61; &#39;-&#39;) a[i] &#61; -a[i];}//处理出初始的信息for(int i &#61; 1; i <&#61; n; i&#43;&#43;){s[i] &#61; s[i-1] &#43; a[i];if(i 1] - t[i];}
// for(int i &#61; 1; i <&#61; n; i&#43;&#43;){
// printf("s[%d] &#61; %d, t[%d] &#61; %d\n", i, s[i], i, t[i]);
// }long long sum1 &#61; 0, sum2 &#61; 0;for(int i &#61; 1; i <&#61; n; i&#43;&#43;){if(s[i] <0){b[&#43;&#43;cnt] &#61; i;sum1 &#43;&#61; 1LL*(-s[i])*t[i];sum2 &#43;&#61; t[i];}}sort(b &#43; 1, b &#43; cnt &#43; 1, cmp);int j &#61; 1;long long k &#61; 0;for(int i &#61; 1; i <&#61; q; i&#43;&#43;){scanf("%d", &c[i].x);c[i].id &#61; i;}sort(c &#43; 1, c &#43; q &#43; 1);for(int i &#61; 1; i <&#61; q; i&#43;&#43;){int x &#61; c[i].x;while(j <&#61; cnt && (-s[b[j]]) <&#61; x){sum1 -&#61; 1LL*(-s[b[j]]) * t[b[j]];sum2 -&#61; t[b[j]];&#43;&#43;j;}if(s[n] &#43; x <0){ans[c[i].id] &#61; -1;}else{ans[c[i].id] &#61; sum1 - x * sum2;}}for(int i &#61; 1; i <&#61; q; i&#43;&#43;){if(ans[i] &#61;&#61; -1) printf("INFINITY\n");else printf("%lld\n", ans[i]);}return 0;
}


推荐阅读
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • Docker的安全基准
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文探讨了如何优化和正确配置Kafka Streams应用程序以确保准确的状态存储查询。通过调整配置参数和代码逻辑,可以有效解决数据不一致的问题。 ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
  • 探索1000以内的完美数:因数和等于自身
    本文探讨了如何在1000以内找到所有完美数,即一个数的因数(不包括自身)之和等于该数本身。例如,6是一个完美数,因为1 + 2 + 3 = 6。通过编程实现这一过程,可以更好地理解完美数的特性。 ... [详细]
author-avatar
王晓宁smile
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有