当前位置: 首页 > news >正文

C. Trinity

https://codeforces.com/problemset/problem/2032/C

题意:给定n个数的数组a,现在可以选择任意i,j,令a[i] = a[j]。问最小的操作次数,可以让数组种任意三个数组成三角形。

思路:需要满足任意的a[i] + a[j] > a[k]。先对a进行排序,然后双指针,右指针r表示让数组中其他所有的数>a[r],左指针表示a[l] + a[l + 1] > a[r],即不需要进行数字变动的一个范围[l, r]。随后,操作数就是r右边的部分和l左边的部分,即n - (r - l + 1)

inline void solve() {int n;cin >> n;vector<int> a(n);for (auto& x : a) {cin >> x;}sort(a.begin(), a.end());int l = 0;int ans = INF;for (int r = 2; r < n; ++r) {//这里相当于,从r往前找第一组a[l]+a[l+1]<=a[r],然后每次都要记录,上一次找到的点,因为上一次如果<a[r],那么这次必然小于,直接往后走就行..//double pointerwhile (r - l > 1 && a[l] + a[l + 1] <= a[r]) {l ++;}ans = min(ans, n - (r - l + 1));}cout << ans << '\n';
}
http://www.zskr.cn/news/46194.html

相关文章:

  • Luogu P9128 [USACO23FEB] Fertilizing Pastures G 题解
  • Docker核心概念:镜像、容器、仓库的本质与关联
  • 【知识分享】怎么建立受控的内外网文件传输通道?
  • 2025年克拉玛依壁挂炉公司权威推荐榜单:威能壁挂炉/万家乐壁挂炉/天然气壁挂炉服务商精选
  • R方分数
  • 如何一键检测并修改公众号文章的错字和敏感词?
  • 2025年列管冷凝器制造企业权威推荐榜单:壳管式冷凝器/石墨冷凝器/蒸发式冷凝器源头厂家精选
  • 第六届机械工程、智能制造与自动化技术国际学术会议 (MEMAT 2025)
  • Windows 批处理bat放开始菜单栏、任务栏
  • 2025年郑州除甲醛公司权威推荐榜单:氧道净醛水漆/新房装修除甲醛/甲醛净化源头服务商精选
  • 分享一个比SQLHC还要厉害的脚本
  • 2025 主流 BPM 厂商全解析:功能、优势与应用场景
  • 软件未来预测的准确性与代码简洁之道
  • 第八周第五天8.5
  • 查询天气预报
  • 基于PCA白化和K均值聚类的轴承故障诊断系统
  • 2025年11月空气能热泵厂家推荐:知名机构榜与口碑评价对比指南
  • 2025年苏州吊车租赁公司权威推荐榜单:龙门吊租赁/升降机租赁/高空作业车租赁公司精选
  • 第八周第三天8.3
  • 在jmx中查询快递
  • 2025年皮带称厂家权威榜单:转子秤/螺旋秤/称重给料机源头厂家精选
  • 在spring项目中,@Resource private ListIGoodsActuator goodsActuators , goodsActuators 是 什么时候初始化的
  • 2025年比较好的船用加热管厂家最新权威实力榜
  • 2025年家用交流稳压器权威推荐榜单:三相稳压器/隧道稳压器/机床稳压器源头厂家精选
  • 剑指offer-36、两个链表的第⼀个公共节点
  • 2025年知名的VR工厂远程云参观用户满意度榜单
  • 2025年靠谱的日本公共交通票价查询方式通票购买指南榜
  • 2025年稳压器厂家权威推荐榜单:家用稳压器/电梯稳压器/机床稳压器源头厂家精选
  • 文件上传大小限制
  • 2025年热门的不锈钢线条TOP品牌厂家排行榜