您的位置:首页 > 健康 > 美食 > 建行官网的网址是多少_四川企业seo_百度seo关键词排名优化工具_谷歌seo外链平台

建行官网的网址是多少_四川企业seo_百度seo关键词排名优化工具_谷歌seo外链平台

2025/3/14 8:41:36 来源:https://blog.csdn.net/m0_62335629/article/details/146243040  浏览:    关键词:建行官网的网址是多少_四川企业seo_百度seo关键词排名优化工具_谷歌seo外链平台
建行官网的网址是多少_四川企业seo_百度seo关键词排名优化工具_谷歌seo外链平台

题目详情

问题描述:

        小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分,代表他的围棋水平。


  小明发现网站的自动对局系统在匹配对手时,只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K,系统都不会将他们匹配。


  现在小明知道这个网站总共有N名用户,以及他们的积分分别是A1, A2, ... AN。


  小明想了解最多可能有多少名用户同时在线寻找对手,但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)?

输入说明:

        第一行包含两个个整数N和K。
   第二行包含N个整数A1, A2, ... AN。


  对于20%的数据,1 <= N <= 10

        对于60%的数据,1 <= N <= 1000

  对于100%的数据,1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

测试用例:

输入:

10 0
1 4 2 8 5 7 1 4 2 8

输出:

6
 

题解

问题分析:

构建DP数组 DP[i]  i是积分的值 DP[i]代表前i个积分最多匹配不到的人数  

注意 当k等于0时 即为对局中积分不同的用户 需要特判

k不等0时 把积分分为K组 只有组内才有可能出现对局匹配 然后依次遍历每一组内 最大的DP[i] 每一组的max和即为ans  因为组内不能选择相邻的 组内积分按照k值递增   

DP数组初始化:

DP[val]数组初始化为有积分val的人数 因为k不等于0的话 那么起码积分相同的人不会匹配对局 没出现的积分全部初始化为0 所以DP数组在创建时就初始化为{0}

DP数组遍历方式:

外层遍历 组 i : 0~k-1 (分成k组 则每一组的起始分别从0~k-1开始)内层遍历组内每一个积分 j :i~Max j+=k (Max为所有玩家中的积分最大值 也是DP数组下标的上限)   

状态转移方程:

            if(j-2*k>=0){
                dp[j]=max(dp[j-k],dp[j-2*k]+cnt[j]);//要选j或者不选j
            }else if(j-k>=0){//j前面只有一个
                dp[j]=max(dp[j],dp[j-k]);
            }

题解代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<set>
#include<sstream>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
int n,k;
int cnt[maxn]={0};//计数 初始化为0
int dp[maxn]={0};//dp[i]表示前i个积分 最多匹配不到的人数
int main(){cin>>n>>k;int val;int Max=-1;//记录最大的积分 方便后续遍历所有积分int sum=0;//统计不同数字的个数 方便k=0特判for(int i=1;i<=n;++i){cin>>val;cnt[val]++;//统计同一个数字有几个if(cnt[val]==1){sum++;//第一次碰到的数字 sum就++}dp[val]++;//dp初始化为val积分出现的个数Max=max(val,Max);//每次更新最大积分值}if(k==0){//k=0特判cout<<sum;return 0;}int ans=0;//分成k组 每一组的开头就是0~k-1 遍历每一组for(int i=0;i<k;++i){int j;//这样每次循环后会保存j的值for(j=i;j<=Max;j+=k){//分类讨论 如果j前面有两个if(j-2*k>=0){dp[j]=max(dp[j-k],dp[j-2*k]+cnt[j]);//要选j或者不选j}else if(j-k>=0){//j前面只有一个dp[j]=max(dp[j],dp[j-k]);}}ans+=dp[j-k];//j-k就是这一组里面最多匹配不到的人数 把每一组加在一起就可以了}cout<<ans;return 0;
}

Code具体说明:

数据结构与变量说明

  • n 和 k 分别表示用户的数量和积分差。
  • cnt[maxn] 用于记录每个积分值出现的次数。
  • dp[maxn] 动态规划数组,dp[i] 表示从积分0到积分i,最多有几个人无法找到对手进行匹配。
  • Max 记录所有输入积分中的最大值,用于后续遍历所有积分。
  • sum 统计不同积分的数量,用于处理k=0的特殊情况。

主要逻辑

  1. 输入处理

    • 首先读取用户数量n和积分差k
    • 然后循环读取每个用户的积分val,并更新cnt[val]以统计每个积分出现的次数。如果某个积分首次出现,则增加sum计数器。
    • 同时初始化dp[val]为该积分出现的次数,并更新Max为当前的最大积分。
  2. 特例处理 (k == 0)

    • 如果k为0,意味着没有两个用户可以匹配,因此直接输出不同积分的数量sum作为结果。
  3. 动态规划求解

    • 对于每个可能的起点i(从0到k-1),尝试将积分分成若干组,每组之间的积分差为k
    • 对于每一组,通过遍历所有可能的积分值j(从i开始,每次增加k),根据前面的状态来决定是否选择当前积分j
      • 如果j-2*k >= 0,则可以选择跳过前一组或两组,选取当前积分j或者不选。
      • 如果j-k >= 0,但j-2*k < 0,则只能考虑是否跳过前一组。
    • 更新ans,它累加了每一组中无法匹配的人数。
  4. 输出结果

    • 最终输出ans,即无法匹配的最多人数。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com