山东第一届省赛 Greatest Number(优雅暴力+二分)

简介: 山东第一届省赛 Greatest Number(优雅暴力+二分)

前言


不愧是第一届省赛,题果然够难,这题wa了15次都没过,一点思路都没;


题目描述:


Saya likes math, because she think math can make her cleverer.


One day, Kudo invited a very simple game:


Given N integers, then the players choose no more than four integers from them (can be repeated) and add them together. Finally, the one whose sum is the largest wins the game. It seems very simple, but there is one more condition: the sum shouldn’t larger than a number M.


Saya is very interest in this game. She says that since the number of integers is finite, we can enumerate all the selecting and find the largest sum. Saya calls the largest sum Greatest Number (GN). After reflecting for a while, Saya declares that she found the GN and shows her answer.


Kudo wants to know whether Saya’s answer is the best, so she comes to you for help.


Can you help her to compute the GN?


大意:有多组数据,每组数据给出N个数,在这N个数里可重复的选择四个数使得最终的加和最接近M;


分析:


首先排除dfs,数据太大了

其次也不是纯暴力,多组数据还是每组最大1000个数

这时候我就错误的想到了多重背包(我觉得实在太像了),但是敲完了一分析还不是多重背包,因为是总共选四个,跟多重背包只是像而已


在结束后看了题解后,发现是一个巧妙的暴力+二分


1.总共有最多1000个数,首先读的时候就先筛一遍,把所有的大于M的数筛掉,这样读进来的数都是有用的;


2.其次做一个O(n2)的处理,把所有符合第一步条件的数两两相加,得到的数进行筛选再次存到数组里,这时数组里存的就是(选一次+选两次)的组合


3.这时候其实我们再用一次上面的操作得到的就是(选一次+选两次+选三次+选四次)的组合,但是会TLE,所以这时候我们要把O(n2)优化成O(nlogn),logn的实现就要请到我们的二分算法来实现;


先上代码:


#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e7+100;
const int p = 1e4;
const double eps = 1e-8;
ll n,m;
int a[N],t,cnt;
ll cnts;
int main()
{
  while(cin>>n>>m) 
  {
  if(m==0||n==0) return 0;//结束条件
  a[0]=0;cnt=0;//初始化
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&t);
    if(t<=m) a[++cnt]=t;  
  }//读入筛选
  int cnt1=cnt;
  for(int i=0;i<=cnt1;i++)
  {
    for(int j=0;j<=cnt1;j++)
    {
    if(a[i]+a[j]<=m) a[++cnt]=a[i]+a[j];
    }
  }//选一次+选两次
  sort(a+1,a+1+cnt);//排序,二分需要数组有序
  int max1=0;
  for(int i=0;i<=cnt;i++)
  {
    int l=i,r=cnt;//二分,注意左边界是 i
    while(l<=r)
    {
    int mid=(l+r)/2;
    if(a[mid]>m-a[i])
      r=mid-1;
    else
    {
      max1=max(max1,a[i]+a[mid]);
      l=mid+1;
    }
    }
  }
  printf("Case %lld: ",++cnts);
  printf("%lld\n\n",max1);
  } 
}


我们还没有解决从(选一次+选两次)到(选一次+选两次+选三次+选四次)这个问题,这时候二分就很好的解决了,我们把二分的对象从 M 变成 M-a[ i ],这时候去二分寻找一个小于等于 M-a[ i ] 的值 ,就完成了上述的转化,也就完成了最多选四个数的目标,即为最后的解法


总结:


这个解法真的非常巧妙,也非常的优雅,先对数组进行了筛选和处理,再进行了二分,思路非常巧妙,非常值得学习;


目录
相关文章
|
Linux
Linux 查看进程PID和线程CPU和内存占用情况
Linux 查看进程PID和线程CPU和内存占用情况
1272 0
|
JSON Java Android开发
Android 开发者必备秘籍:轻松攻克 JSON 格式数据解析难题,让你的应用更出色!
【8月更文挑战第18天】在Android开发中,解析JSON数据至关重要。JSON以其简洁和易读成为首选的数据交换格式。开发者可通过多种途径解析JSON,如使用内置的`JSONObject`和`JSONArray`类直接操作数据,或借助Google提供的Gson库将JSON自动映射为Java对象。无论哪种方法,正确解析JSON都是实现高效应用的关键,能帮助开发者处理网络请求返回的数据,并将其展示给用户,从而提升应用的功能性和用户体验。
274 1
|
Python
【Python】已解决:(from docx import Document导包报错)ModuleNotFoundError: No module named ‘exceptions’
【Python】已解决:(from docx import Document导包报错)ModuleNotFoundError: No module named ‘exceptions’
1419 0
|
存储 安全 网络协议
数字时代的守护者:网络安全与信息安全的重要性
在数字化浪潮中,网络安全与信息安全成为保护个人隐私和企业资产的盾牌。本文将探讨网络漏洞的成因、加密技术的应用以及安全意识的培养,旨在为读者提供防范网络威胁的知识武器,共同构建更安全的网络环境。
|
算法框架/工具 异构计算 索引
Transformers 4.37 中文文档(三十七)(5)
Transformers 4.37 中文文档(三十七)
100 0
|
XML JavaScript 前端开发
只使用JS怎么给静态网页添加站内全局搜索功能?
只使用JS怎么给静态网页添加站内全局搜索功能?
232 0
只使用JS怎么给静态网页添加站内全局搜索功能?
|
Java
JavaSE——集合框架二(2/6)-综合案例-斗地主游戏(做牌、洗牌、发牌、排序、看牌)
JavaSE——集合框架二(2/6)-综合案例-斗地主游戏(做牌、洗牌、发牌、排序、看牌)
70 0
|
传感器 监控 安全
如何理解企业安全能力框架(IPDRR)
企业安全能力框架(IPDRR)是美国国家标准与技术研究所(National Institute of Standards and Technology)的网络安全框架(简称NISTCSF )。第一个版本于2014年发布,旨在为寻求加强网咯安全防御的组织提供指导。企业可以根据自身需求加强网络安全防御。随着社会数字化转型的深入,网络攻击事件日益增多、破坏力逐步增强。安全方法论也正逐步从"针对威胁的安全防御"向“面向业务的安全治理”(IPDRR)等演进。 IPDRR能力框架模型包括风险识别(Identify)、安全防御(Protect)、安全检测(Detect)、安全响应(Response)和安全
2881 0
|
前端开发 搜索推荐
帝国CMS自适应网址导航网站模板代码
帝国CMS自适应网址导航网站模板代码分享
139 2
|
前端开发 数据库连接 数据库
SpringMVC实现增删改查(CRUD)--全面详细讲解
SpringMVC实现增删改查(CRUD)--全面详细讲解
218 0