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

CF1490EAccidentalVictory(前缀和)

题目传送门这道题我们来寻找性质,用一个结构体来存储数据的值和数据的位置,并对数据的值将进行排序,并求前缀和,如果i-1的前缀

题目传送门
这道题我们来寻找性质,用一个结构体来存储数据的值和数据的位置,并对数据的值将进行排序,并求前缀和,如果i-1的前缀和小于a[i]那么答案就一定不在1~i-1之间了,答案在i ~ n这个区间,因此记录下来,最后的ans以后的所有位置用一个数组存放起来,再对这个数组排序,最后的答案就是这个数组的数据。

#include
#include
#include
using namespace std;
typedef long long ll;
struct node{ll num;ll p;
}s[2102100];
ll sum[2102120];
ll an[21020000];
bool cmp(node x,node y){return x.num<y.num;
}
int main(){ll T;cin>>T;while(T--){ll n;cin>>n;for(ll i&#61;1;i<&#61;n;i&#43;&#43;){cin>>s[i].num;s[i].p&#61;i;} sort(s&#43;1,s&#43;1&#43;n,cmp);for(ll i&#61;1;i<&#61;n;i&#43;&#43;){sum[i]&#61;s[i].num&#43;sum[i-1];}ll ans&#61;1;//记录起始位置 for(ll i&#61;1;i<&#61;n;i&#43;&#43;){if(sum[i-1]<s[i].num)ans&#61;i;if(sum[i-1]&#61;&#61;0)ans&#61;i;}if(sum[n]&#61;&#61;0)ans&#61;n&#43;1;ll o&#61;0;for(ll i&#61;ans;i<&#61;n;i&#43;&#43;)an[&#43;&#43;o]&#61;s[i].p;if(ans<&#61;n)sort(an&#43;1,an&#43;1&#43;o);printf("%lld\n",o);for(ll i&#61;1;i<&#61;o;i&#43;&#43;)printf("%lld ",an[i]);printf("\n");}return 0;
}


推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
author-avatar
实圪垯电动乐园_855
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有