首页 > 其他分享 >C. Array Game

C. Array Game

时间:2024-04-12 15:24:23浏览次数:22  
标签:min ll else Game abs ans Array d1

原题链接

题解

1.突然遇到新颖的题,我们可以采用逐步变难法、最简策略法、观察数据法
逐步变难法:
当 \(k=0\) 时, \(ans_0=min(a[i])\)
\(k=1\) 时 \(ans_1=min(ans_0,a[i]-a[i+1](sort))\)
观察数据法:
\(k=2\) 时 观察数据可知 \(n^2\) 左右的算法是可行的,所以我们可以先两端循环遍历所有的第一次 \(|a[i]-a[j]|\) ,再二分查找出最接近的值
易错提醒!!:最小值是数组中的最小值而不是相减后的最小值所以还要有一步 \(ans_2=min(ans_2,ans_1,ans_0)\)
最简策略法:
当 \(k=3\) ,可以前两次得到相同值,第三次得到0,然后无限循环

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[2005]={0};
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        for(ll i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1,greater<ll>());

        if(k>=3)puts("0");
        else if(k==1)
        {
            ll ans=2e18;
            for(ll i=1;i<n;i++) ans=min(ans,a[i]-a[i+1]);
            for(ll i=1;i<=n;i++) ans=min(ans,a[i]);
            cout<<ans<<endl;
        }
        else
        {
            ll ans=2e18;
            for(ll i=1;i<n;i++) ans=min(ans,a[i]-a[i+1]);
            for(ll i=1;i<=n;i++) ans=min(ans,a[i]);
            for(ll i=1;i<=n-1;i++)
            {
                for(ll j=i+1;j<=n;j++)
                {
                    ll l=1,r=n+1;
                    ll d1=a[i]-a[j];
                    while(l+1<r)
                    {
                        ll mid=(l+r)/2;
                        if(a[mid]>=d1) l=mid;
                        else r=mid;
                    }
                    if(l!=n) ans=min(min(abs(d1-a[r]),abs(d1-a[l])),ans);
                    else ans=min(ans,abs(d1-a[l]));
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

标签:min,ll,else,Game,abs,ans,Array,d1
From: https://www.cnblogs.com/pure4knowledge/p/18131338

相关文章

  • lodash已死?radash最全使用介绍(附源码说明)—— Array方法篇(3)
    前言我们已经介绍了radash的相关信息和部分Array相关方法,详情可前往主页查看;本篇我们继续介绍radash中Array的相关方法;下期我们将介绍解析radash中剩余的Array相关方法,并整理出Array方法使用目录,包括文章说明和脑图说明。Radash的Array相关方法详解iterate:把一个函数迭代......
  • [题解][2022江西省程序设计大赛] A Game of Taking Numbers
    题目描述rqdmap和他的小女友正在玩一个游戏。有n个正整数。这两个人轮流取数字。为了显示他的绅士风度,rqdmap要求他的小女友先取数字。每当rqdmap的小女友可以选择剩下的数字中的任意一个来拿走(记为x),rqdmap需要从剩下的数字中选择一个数字(记为y),并且满足以下两个条件中的至少一个......
  • Suffix Array
    简介后缀数组(或者叫后缀排序算法),能够将一个字符串每一个后缀按照字典序排序。暴力的\(\mathcal{O}(n^{2}\logn)\)不用细讲,使用哈希优化后的\(\mathcal{O}(n\log^{2}n)\)也不讲。\(\mathcal{O}(n\log^{2}n)\)做法一些定义:\(sa_{i}\)表示后缀排序后,排名为\(i\)的......
  • Java中Array.sort()的几种用法简明教程 (需要初始化要排序的对象)对 一个数组的所有元素
    Java中Array.sort()的几种用法简明教程(需要初始化要排序的对象)对一个数组的所有元素进行排序,并且是按从小到大的顺序Java中Array.sort()的几种用法简明教程(需要初始化要排序的对象)======================================================1、Arrays.sort(int[]a)......
  • JavaScript Array方法汇总
    函数名定义返回值是否改变原数组是否生成新数组push向数组的末尾添加一个或多个元素返回新的数组长度是否pop删除并返回数组的最后一个元素返回数组的最后一个元素是否unshift向数组的开头添加一个或多个元素返回新的数组长度是否shift删除数组的第一项返回第一个元素的值。若......
  • org.apache.commons.lang3.ArrayUtils 学习笔记
    1234567891011121314151617181920212223242526272829303132333435package com.nihaorz.model; /** *@作者王睿 *@时间2016-5-17上午10:05:17 * */public class Person{    private Stringid;    pr......
  • Increase Subarray Sums
    原题链接题解观察数据范围,看到\(n<=5000\)便确定了\(O(n^2)\)左右的算法,这样一来我可以遍历所有的区间虽然每个\(f(k)\)对应的答案区间都不同,但一定能遍历到,所以我可以再遍历一遍k,算出以该区间为答案区间时的\(f(k)\)但是这样一来时间复杂度就超了,于是能不能优化?假如......
  • CF1913C Game with Multiset 题解
    翻译初始时你有一个空序列,共\(m\)次操作,每次操作读入两个数\(t_i\),\(v_i\),分为以下两种操作:当\(t_i=1\)时,在空序列中加入\(2^{v_i}\)这一元素。(此时\(0\lev_i\le29\))当\(t_i=2\)时,询问是否存在:取当前序列的某些元素,使它们的的和等于\(v_i\)(此时\(0\lev_i\l......
  • CF1815A Ian and Array Sorting 题解
    题面。直接进入主题吧。思路题目要求非递减序列,很明显,由题目给的操作,一定可以将这个序列的前\(n-1\)项能够满足是非递减序列,最后只需要比较第\(n\)项是否大于等于第\(n-1\)项即可。解释一下为什么。对于序列\(a\),从\(a_1\)开始到\(a_{n-1}\)结束,每次对\(a_i\)......
  • MXnet安装 与入门 符号式运算 Symbol 数据同步 KVStore 自动并行计算 数据的导出与载
    MXnet参考通过MXNet/Gluon来动手学习深度学习在线githubpdf代码深度学习库MXNet由dmlc/cxxnet,dmlc/minerva和Purine2的作者发起,融合了Minerva的动态执行,cxxnet的静态优化和Purine2的符号计算等思想,直接支持基于Python的parameterserver接口,使......