首页 > 其他分享 >CF1121B Mike and Children 题解

CF1121B Mike and Children 题解

时间:2022-08-25 11:56:08浏览次数:107  
标签:Mike 标记 int 题解 答案 include Children

题意翻译十分简洁,我说几点需要注意的。

最多能选几个数?

这是错的,要给出最多选出几对数。

现在我们就珂以开始了。

我的做法理论时间复杂度是 O(n^3)O(n3) 的暴力,但是因为常数较小于是珂以通过。

首先我们观察发现 a_iai​ 的范围很小,只有 10^5105 于是我们把给出的数标记一下。

scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),vis[a[i]]=1;
//标记一下a[i]方便后面查找

然后枚举任意两个数,得到一个和 a_i+a_j(i\not=j)ai​+aj​(i​=j) 再循环一次,判断 a_i+a_j-a_kai​+aj​−ak​ 是否被之前标记过,如果被标记过,那么说明这个答案珂行,把当前答案加一,最后统计最大值即可。

注意以下两点:

  • 防止数组越界,当 (a_i+a_j-a_k)<1(ai​+aj​−ak​)<1 时直接跳过。

  • 最后答案两两统计过,所以答案要除以二。

#include<cstdio>
#include<algorithm>
#define N 1919810
using namespace std;
int n,a[N],l,r,ans;
bool vis[N];
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),vis[a[i]]=1;
    for(int ii=1;ii<=n;ii++){
        for(int jj=ii+1;jj<=n;jj++){
            int v=a[ii]+a[jj],cnt=0;
            for(int i=1;i<=n;i++){
                if(v-a[i]<=0)continue;
                if(vis[v-a[i]])cnt++;
            }
            cnt/=2;
            ans=max(ans,cnt);
        }
    }   
    printf("%d",ans);
    return 0;
}
 

标签:Mike,标记,int,题解,答案,include,Children
From: https://www.cnblogs.com/masida-hall-LZ/p/16623834.html

相关文章

  • @RequestBody注解转对象中驼峰格式的参数无法接收到数据的问题解决方法
    1.问题:驼峰格式的参数传递到后端,@RequestBody注解标注的实体对象参数没有接收到对应的数据前端传参:执行结果:请求参数实体:importlombok.Data;/***请求参数*@author......
  • CSP 202006-1 202006-2 题解
    #202006-1线性分类器在坐标系中,我们可以考虑使用同一横坐标x值对应的y值来判断在直线的上方一侧还是在下方一侧。当然,如果不在坐标系中也可以统计点和直线的位置关系,这......
  • B3620 题解
    题目传送门\(\color{red}{see}\space\color{green}{in}\space\color{blue}{my}\space\color{purple}{blog}\)小学生又双叒叕来写题解啦!这题是\(x\)进制转\(10\)......
  • CF1646B 题解
    题目传送门\(\color{red}{see}\space\color{green}{in}\space\color{blue}{my}\space\color{purple}{blog}\)看到题解里没有用双指针往中间靠的写法的,果断来一发。思......
  • CF1624C 题解
    题目传送门\(\color{red}{see}\space\color{green}{in}\space\color{blue}{my}\space\color{purple}{blog}\)小学生又双叒叕来写题解啦!这题还是很简单的,甚至不需要像......
  • CF1617B 题解
    题目传送门\(\color{red}{see}\space\color{green}{in}\space\color{blue}{my}\space\color{purple}{blog}\)小学生又双叒叕来写题解啦!其他题解的代码都是\(O(1)\)......
  • CF402A 题解
    题目传送门\(\color{red}{see}\space\color{blue}{in}\space\color{green}{my}\space\color{purple}{blog}\)小学生又双叒叕来写题解啦!看到其他题解描述得并不清晰,我......
  • AT4894 题解
    题目传送门小学生又双叒叕来写题解啦!翻了一下大家的思路,都用了数组,其实根本不用,可以一边读入一边判断。由于只需考虑前后两个数,所以只用两个变量就能实现滚动数组。若......
  • AT4783 题解
    题目传送门小学生又双叒叕来写题解啦!这题的关键就是贪心。看到N的范围,瞬间明白可能要排序。所以我们靠着排序来想。我们来思考一下怎样安排顺序。对于两个时间限......
  • AT4891 题解
    题目传送门小学生又双叒叕来写题解啦!这题的翻译貌似不完整。所谓怪兽与英雄的对决,就是双方同时扣同样的血,直到一方为零。弄懂题后,你会发现,这题不是考贪心,而是模拟。写......