Codeforces Round #544 (Div. 3) C. Balanced Team [暴力剪枝]

Stella981
• 阅读 664

You are a coach at your local university. There are n n students under your supervision, the programming skill of the i i -th student is a i ai . You have to create a team for a new programming competition. As you know, the more students some team has the more probable its victory is! So you have to create a team with the maximum number of students. But you also know that a team should be balanced. It means that the programming skill of each pair of students in a created team should differ by no more than 5 5 . Your task is to report the maximum possible number of students in a balanced team. Input The first line of the input contains one integer n n ( 1≤n≤2⋅ 10 5 1≤n≤2⋅105 ) — the number of students. The second line of the input contains n n integers a 1 , a 2 ,…, a n a1,a2,…,an ( 1≤ a i ≤ 10 9 1≤ai≤109 ), where a i ai is a programming skill of the i i -th student. Output Print one integer — the maximum possible number of students in a balanced team. Examples Input Copy 6 1 10 17 12 15 2 Output Copy 3 Input Copy 10 1337 1337 1337 1337 1337 1337 1337 1337 1337 1337 Output Copy 10 Input Copy 6 1 1000 10000 10 100 1000000000 Output Copy 1 #####题解:题意给n个数,求子集的最小值和最大值之差不超过5,求最大的子集的元素数. #####我的思路:先对数组排序,这里如果直接暴力的话,O(n^2)的复杂度,肯定会tle, #####优化一下,因为是排过序的,所以子集的左端和右端都是极值,如果右值与左值之差大于5,左值的位置右移, ####再次优化,如果前一值与后一值之差大于5,I 移动的后一值的位置.

#include <bits/stdc++.h>
const int N=2e5+5;
using namespace std;
int a[N],b[N];
int ans=0,cnt=0,flag=0,maxn=0;
void check(int m){
    if(m>maxn) maxn=m;
}
int cal(int i,int j){
    return a[j]-a[i];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    int i=1,j=i+1;
    while(i<=n-1&&j<=n){
        if(cal(j-1,j)>5){
            check(j-1-i);
            i=j;
            j++;
        }
        else if(cal(i,j)>5){
            check(j-1-i);
            i++;
            if(i==j) j++;
            //cout<<"jjg"<<endl;
        }
        else{
            j++;
            //cout<<"jj"<<endl;
        }
        //if(!flag) break;
    }
    check(j-1-i);
    printf("%d\n",maxn+1);
    return 0;
}
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
AndroidStudio封装SDK的那些事
<divclass"markdown\_views"<!flowchart箭头图标勿删<svgxmlns"http://www.w3.org/2000/svg"style"display:none;"<pathstrokelinecap"round"d"M5,00,2.55,5z"id"raphael
Stella981 Stella981
3年前
Codeforces Round #479 (Div. 3) F. Consecutive Subsequence
标签:DP题目链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F977%2Fproblem%2FF)
Stella981 Stella981
3年前
Codeforces Round #590 (Div. 3)
D. DistinctCharactersQueriesDescriptionYouaregivenastring ss consistingoflowercaseLatinlettersand qq queriesforthisstri
Stella981 Stella981
3年前
Codeforces Round #608 (Div. 2) 题解
\TOC\CodeforcesRound608(Div.2)题解前言题目链接:仅仅只是为了方便以题目作为关键字能查找到我的题解而已(逃Codeforces1271A(https://www.oschina.net/action/GoToLink?u
Stella981 Stella981
3年前
Codeforces Round #611 (Div. 3)
原题面:https://codeforces.com/contest/1283(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1283)A.MinutesBeforetheNewYear题目大意:给定时间,问距离零点
Stella981 Stella981
3年前
Educational Codeforces Round 73 (Rated for Div. 2)
传送门(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1221)A.2048Game乱搞即可。<details<summaryCode</summaryinclude<bits/std
Stella981 Stella981
3年前
Codeforces Round #616 (Div. 2)
A.EvenButNotEven(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F1291%2Fproblem%2FA)题意:给你一个很长的数,可以删减里面的任意数字,要求本身不能除以2,但是该数的各位和能除以2,输出任意符合
Stella981 Stella981
3年前
Codeforces Round #565 (Div. 3) C. Lose it!
链接:https://codeforces.com/contest/1176/problem/C(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1176%2Fproblem%2FC)题意:Youare