genius ACM

genius ACM

蒟蒻认为这道题好难。看了题解也并不能完全理解。
主要难度在对倍增的理解上~~(其实归并排序也并不懂)~~

题面描述

给定一个整数 M,对于任意一个整数集合 S,定义“校验值”如下:
从集合 S 中取出 M 对数(即 2×M 个数,不能重复使用集合中的数,如果 S 中的整数不够 M 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 S 的“校验值”。

现在给定一个长度为 N 的数列 A 以及一个整数 T。
我们要把 A 分成若干段,使得每一段的“校验值”都不超过 T。

求最少需要分成几段。

关于二分写法,时间复杂度暂不证明(蒟蒻不会)

我们考虑如何解题
我们先思考如何使每对数的差的平方之和最大,我们考虑贪心,为使差最大,我们可以找出最大值与最小值,我们可以一直这样找 M对。

然后我们要想题的限制条件
我们的答案要求分成的段数最少
那我们使每段的长度尽可能的延长
我们可以固定左端点,使右端点尽可能的长
问题就转化为了求一个右端点在不超过校验值T的时候,最大为多少。
我们可以去二分一个右端点,但在右端点与左端点相近的时候,表现较差。
处理此类问题也可以用倍增
我们每次可以使右端点向后走2的i次方,然后求出校验值,看是否合法,直到我们找到右端点的位置
对于未排序的的区间,可以用归并排序解决

那这道题差不多就可以了

/***********************************************************
  > File Name: genius(acm).cpp
  > Author: lan_m
  > QQ: 2867930696
  > Created Time: 2021/9/15 20:45:22
  > fighting for night
 *******************************************************/

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 5e5+10;
int n,m,Q;
int a[N],b[N],c[N];

void merge(int l,int mid,int r) {
	int i = l,j = mid+1,k = l;
	while (i <= mid && j <= r) {
		if (c[i] <= c[j]) b[k++] = c[i++];
		else b[k++] = c[j++];
	}
	while (i <= mid) b[k++] = c[i++];
	while (j <= r) b[k++] = c[j++];
}
bool check(int s,int mid,int e) {
	for (int i = mid+1;i <= e;i ++) c[i] = a[i];
	sort(c+mid+1,c+e+1);
	merge(s,mid,e);
	int sum = 0;
	for (int i = 1;i <= (e - s + 1)>>1 && i <= m;i ++) {
		sum += (b[e-i+1] - b[s+i-1]) * (b[e-i+1] - b[s+i-1]);
	}
	if (sum <= Q) {
		for (int i = s;i <= e;i ++) c[i] = b[i];
		return true;
	}
	return false;
}

signed main () {
	int T;scanf("%lld",&T);
	while (T--) {
		scanf("%lld%lld%lld",&n,&m,&Q);
		for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);
		int p = 1,ans = 0;
		int st = 1,ed = 1;
		c[1] = a[1];
		while (ed <= n) {
			if (p == 0) {
				p = 1;
				ans ++;
				st = ed + 1;
				ed += 1;
				c[st] = a[st];
			}
			else if (ed + p <= n && check(st,ed,ed+p)) {
			    ed = ed + p;
			    p <<= 1;
			    if (ed == n)break;
			}
			else p>>=1;
		}
		if( ed == n ) ans ++;
		printf("%lld\n",ans);
	}
	return 0;
}

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数&#xff1a; gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点&#xff1a; 完后运行&#xff0c;r gdb 中的有用命令 下面是一个有用的 gdb 命令子集&#xff0c;按可能需要的顺序大致列出。 第一列给出了命令&#xff0c;可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布&#xff1a; 一元高斯分布&#xff1a;(将多元高斯分布中的D取值1&#xff09; 其中代表的是平均值&#xff0c;是方差的平方&#xff0c;也可以用来表示&#xff0c;是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要&#xff0c;需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容&#xff0c;经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch &#xff0c;简称ES 。是一个全文搜索服务器&#xff0c;也可以作为NoSQL 数据库&#xff0c;存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项&#xff1a; (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候&#xff0c;访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议&#xff1a;以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么&#xff1f; 在java规范中是这样描述的&#xff1a;Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联&#xff0c;线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统&#xff0c;该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口&#xff0c;远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能&#xff0c;出了大概一年了。 程序员们在编程时遇到不会的问题&#xff0c;又没有老师可以提问&#xff0c;就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法&#xff0c;但是不一定得到回复&#xff0c;…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎&#xff0c;题目很狗&#xff0c;第一次踩这个坑&#xff0c;单拉出来写个题解记录一下 题意&#xff1a;给一个数字矩阵&#xff0c;一次操作&#xff1a;对于每一行&#xff0c;可以去掉左端或者右端的数&#xff0c;得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1&#xff09;全特化2&#xff09;偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类&#xff1a; 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…