精华内容
下载资源
问答
  • 中位数

    2019-08-12 16:41:43
    至多k次操作之后,数组的中位数最大能变成多少。 输入格式: 多组输入 第一行个整数n,k(1≤n≤2×10​5​​,1≤k≤10​9​​)。 第二行n和整数a​1​​,a​2​​,......,a​n​​。 输出格式: k次操作后...

    一个有 n 个整数的数组 a,n是一个奇数。

    每次可以选择数组里的一个元素 a​i​​ 并把这个元素加上 1。

    在至多 k 次操作之后,数组的中位数最大能变成多少。

    输入格式:

    多组输入

    第一行两个整数 n,k(1≤n≤2×10​5​​,1≤k≤10​9​​)。

    第二行 n 和整数 a​1​​,a​2​​,......,a​n​​。

    输出格式:

    k 次操作后数组的中位数。

    输入样例:

    3 2
    1 3 5
    

    输出样例:

    5

    首先,用最普通的想法就是从中位数开始往后一个数一个数地找找到可以实现的最大中位数的值;第二种方法用二分法来枚举中位数,看是否可行;这个题注意ai的范围没有说明,可能超过int范围,所以记得用long long

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+10;
    ll a[maxn],b[maxn];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        int n,k;
        while(cin>>n>>k)
        {
            for(int x=1;x<=n;x++)
            {
                cin>>a[x];
            }
            sort(a+1,a+n+1);
            ll z=(n+1)/2;
            for(int x=z;x<n;x++)
            {
                b[x+1]=a[x+1]-a[x];
            }
            ll ans=a[z],w=1;
            while(k>0)
            {
                if(k-b[z+w]*w>=0&&z+w<=n)
                {
                    k-=b[z+w]*w;
                    //cout<<k<<endl;
                    ans=a[z+w];
                    w++;
                }
                else
                {
                    ans+=k/w;
                    break;
                }
            }
            cout<<ans<<endl;
        }
    }
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <vector>
    #include <string>
    using namespace std;
    #define int long long
    int x[200010];
    signed main()
    {
        int n,k;
        while(~scanf("%d %d",&n,&k))
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d",&x[i]);
            }
            sort(x,x+n);
            int l=x[n/2],r=x[n-1]+k/(n/2+1);
            int mid=(l+r)/2;
            //int ans;
            while(l<=r)
            {
                int t=k;
                for(int i=n/2;x[i]<mid && i<n;i++)
                {
                    t-=(mid-x[i]);
                    if(t<0)
                    {
                        break;
                    }
                }
                if(t<0)
                {
                    r=mid-1;
                    mid=(l+r)/2;
                } else
                {
                    //ans=mid;
                    l=mid+1;
                    mid=(l+r)/2;
                }
                //printf("%d %d %d\n",l,r,mid);
            }
            printf("%d\n",l-1);
        }
        return 0;
    }

     

    展开全文
  • 当n为奇数时,中位数是唯一,出现i=(n+1)/2处;当n为偶数时,存在中位数,分别出现i=n/2处和i=n/2+1处 2、找出集合中的最大和最小元素需要比较多少次? 找出集合中的最大元素比较上界n-1次,最小...

    中位数和顺序统计学

    • 中位数和顺序统计学
    • 0、在一个由n个元素组成的集合中,第i个顺序统计量是该集合中第i小的元素
    • 1、中位数是它所在集合的“中点元素”;当n为奇数时,中位数是唯一的,出现在i=(n+1)/2处;当n为偶数时,存在两个中位数,分别出现在i=n/2处和i=n/2+1处
    • 2、找出集合中的最大和最小元素需要比较多少次?
    • 找出集合中的最大元素的比较上界是n-1次,最小元素也是一样
    • 3、如果要找出最大和最小元素,看起来需要2n-2次;事实上至多3(n/2)次比较就足以同时找到最大和最小元素:
    • 成对的处理元素,先将一对元素互相比较,然后把较小的与当前最小元素比较,把较大的与当前最大元素比较,因此每两个元素需要比较3次
    • 如何设定当前最大和最小值的初始值依赖于n是奇数还是偶数;如果n是奇数,就将最大值和最小值都设为第一个元素的值,然后成对的处理余下的元素;如果n是偶数,就对前两个元素做一次比较,以决定最大值和最小值的初值,然后如同n是奇数的情况一样,成对的处理余下的元素
    • 4、期望情况为线性时间的选择:
    • 期望时间复杂度:O(n)
    • 最坏时间复杂度:O(n*n) 

    情况好的情况: 

    int Partition1(int ary[], int left, int right)    //快排的划分函数
    {
    	int i = left - 1;
    	for (int j = left; j < right; ++j)
    		if (ary[j] <= ary[right])
    		{
    			++i;
    			swap(ary[i], ary[j]);
    		}
    	swap(ary[i + 1], ary[right]);
    	return i + 1;
    }
    int RandomizedPartition(int ary[], int left, int right)    //快排的随机划分
    {
    	srand((unsigned)time(NULL));
    	int rdm = rand() % (right - left) + left;
    	swap(ary[right], ary[rdm]);
    	return Partition1(ary, left, right);
    }
    int RandomizedSelect(int ary[], int left, int right, int i)
    {                        //返回的是第i小的元素
    	if (left == right)
    		return ary[left];
    	int rdm = RandomizedPartition(ary, left, right);    //rdm是划分之后主元的下标
    	int k = rdm - left + 1;    //k是主元在当前区间中的第几个
    	if (i == k)    //如果当前主元的位置k等于i,那么k对应的下标r就是所求元素的下标
    		return ary[rdm];
    	else if (i < k)
    		return RandomizedSelect(ary, left, rdm - 1, i);
    	else
    		return RandomizedSelect(ary, rdm + 1, right, i - k);
    	//为什么i-k ?
    	//因为已经知道有k个元素(即ary[left..rdm]中的所有元素)小于ary[left..right]
    	//中的第i小元素,所以所求元素必是ary[rdm+1..right]中的第i-k小的元素
    }
    
    
    void testRandomizedSelect()
    {
    	int a[10] = { 0,45,57,89,100,70,35,39,20,53 };
    	for (int i = 1; i < 11; ++i)
    	{
    		cout << "第" << i << "小的数为:";
    		cout << RandomizedSelect(a, 0, 9, i) << endl;
    	}
    
    }

     结果:

    结果:
    第1小的数为:0
    第2小的数为:20
    第3小的数为:35
    第4小的数为:39
    第5小的数为:45
    第6小的数为:53
    第7小的数为:57
    第8小的数为:70
    第9小的数为:89
    第10小的数为:100

    情况最坏的情况:

    //最坏情况
    int SelectPartition(int ary[], int left, int right, int pivot)
    {
    	int i = left - 1, j;
    	for (j = left; j <= right; ++j)
    		if (ary[j] == pivot)    //找到pivot的下标
    			break;
    	swap(ary[j], ary[right]);
    	for (j = left; j < right; ++j)
    		if (ary[j] <= pivot)
    		{
    			++i;
    			swap(ary[i], ary[j]);
    		}
    	swap(ary[i + 1], ary[right]);
    	return i + 1;
    }
    void InsertionSort(int ary[], int left, int right)
    {
    	for (int i = left + 1; i <= right; ++i)
    	{
    		int t = ary[i];
    		int j = i - 1;
    		while (j >= left && ary[j] > t)    //注意:略做修改,是j>=left
    		{
    			ary[j + 1] = ary[j];
    			--j;
    		}
    		ary[j + 1] = t;
    	}
    }
    int Select(int ary[], int left, int right, int i)
    {                        //返回的是第i小的元素
    	if (right - left < 5)
    	{
    		InsertionSort(ary, left, right);
    		return ary[left + i];
    	}
    	int l, r;
    	for (int j = 0; j < (right - left + 5) / 5; ++j)
    	{
    		l = left + j * 5,    //确定分组的left
    			r = (left + j * 5 + 4) > right ? right : left + j * 5 + 4;    //确定分组的right
    		InsertionSort(ary, l, r);    //排序当前分组
    		swap(ary[left + j], ary[l + (r - l) / 2]);    //将各分组的中位数依次交换到前面
    	}
    	l = left;
    	r = left + (right - left) / 5;    //定位移动之后的最右边中位数的位置,中位数的区间
    	int pivot = Select(ary, l, r, (r - l) / 2);    //中位数的中位数
    	int m = SelectPartition(ary, left, right, pivot);    //用中位数来划分
    	int x = m - left;    //左边m-left个元素,右边right-m-1个元素,中间的是划分元素
    	if (i == x)
    		return ary[m];
    	else if (i < x)
    		return Select(ary, left, m - 1, i);
    	else
    		return Select(ary, m + 1, right, i - x - 1);
    }
    
    void testSelect()
    {
    	int a[10] = { 0,45,57,89,100,70,35,39,20,53 };
    	for (int i = 0; i < 10; ++i)
    	{
    		cout << "第" << i << "小的数为:";
    		cout << Select(a, 0, 9, i) << endl;
    	}
    }

    结果:

    结果:
    第1小的数为:0
    第2小的数为:20
    第3小的数为:35
    第4小的数为:39
    第5小的数为:45
    第6小的数为:53
    第7小的数为:57
    第8小的数为:70
    第9小的数为:89
    第10小的数为:100

    希尔排序

    • 希尔排序
    • 将无序数组分割为若干个子序列。
    • 子序列不是逐段分割的,而是相隔特定的增量的子序列。
    • 对各个子序列进行插入排序;然后再选择一个更小的增量。
    • 再将数组分割为多个子序列进行排序......最后选择增量为1。
    • 即使用直接插入排序,使最终数组成为有序。
    • 耗费的时间是O(n^2)
    • 希尔排序是插入排序的高级版

     排序过程:

    void ShellSort(int r[], int n)
    {
    	int i;
    	int d;
    	int j;
    	for (d = n / 2; d >= 1; d = d / 2)            //以增量为d进行直接插入排序
    	{
    		for (i = d + 1; i < n; i++)
    		{
    			r[0] = r[i];                 //暂存被插入记录
    			for (j = i - d; j > 0 && r[0] < r[j]; j = j - d)
    				r[j + d] = r[j];       //记录后移d个位置
    			r[j + d] = r[0];
    		}
    	}
    	for (i = 1; i < n; i++)
    		cout << r[i] << " ";
    }
    
    void testShellSort()
    {
    	int array[10] = { 0,6,1,2,4,7,8,9,3,5 };
    	cout << "arr is old :";
    	for (int i = 1; i < 10; i++)
    	{
    		cout << array[i] << " ";
    	}
    	cout << endl;
    	ShellSort(array, 10);  //排序后
    	cout << endl;
    	cout << "arr is new :";
    	for (int i = 1; i < 10; i++)
    	{
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }

    结果:

    结果:
    arr is old :6 1 2 4 7 8 9 3 5
    1 2 3 4 5 6 7 8 9
    arr is new :1 2 3 4 5 6 7 8 9

     

    展开全文
  • 7-4 中位数 (10分)

    2020-02-23 17:06:45
    至多 k 次操作之后,数组的中位数最大能变成多少。 输入格式: 多组输入 第一行个整数 n,k(1≤n≤2×10​5​​,1≤k≤10​9​​)。 第二行 n 和整数 a​1​​,a​2​​,......,a​n​​。 输出格式: k 次...

    一个有 n 个整数的数组 a,n是一个奇数。

    每次可以选择数组里的一个元素 a​i​​ 并把这个元素加上 1。

    在至多 k 次操作之后,数组的中位数最大能变成多少。

    输入格式:

    多组输入

    第一行两个整数 n,k(1≤n≤2×10​5​​,1≤k≤10​9​​)。

    第二行 n 和整数 a​1​​,a​2​​,......,a​n​​。

    输出格式:

    k 次操作后数组的中位数。

    输入样例:

    3 2
    1 3 5
    

     

    输出样例:

    5

    千万千万要注意:

    多组输入!!!!!!

    超大数据!!!!!!10^9

    long long int

     

    思路:

    先排序后确定中位数

    如果想要中位数最大,则中位数<=后面任意一个数

    所以每次使中位数a[h]尽量接近a[h+flag]

    如果剩余的k大于差值,则要使中位数到a[h+flag]之间的数都加上差值

    否则,使k/flag,使中间的数均加上k/flag;

     

    #include<cstdio>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int n;
    long long m;
    int main(){
    	
    	while(cin>>n>>m){
    		int a[n];
    		for(int i=0;i<n;i++){
    			cin>>a[i];
    		}
    		sort(a,a+n);
    		long long int h=(n-1)/2;
    		long long int flag=1;
    		while(m!=0){
    			if(h+flag>n-1){
    				a[h]+=m/flag;
    				m=0;
    				break;
    			}
    	        long long int t=a[h+flag]-a[h];
    			if(m>=t*flag){
    				m-=t*flag;
    				a[h]+=t;
    			}
    			else{
    				a[h]+=m/flag;
    				m=0;
    			}
    			flag++;
    		}
    		cout<<a[h]<<endl;
    	}
    	
    }

     

    展开全文
  • PTA 7-4 中位数 (10分)

    2020-02-24 14:56:12
    至多 kkk 次操作之后,数组的中位数最大能变成多少。 输入格式: 多组输入 第一行个整数 n,k(1≤n≤2×10​5,1≤k≤109)n,k(1≤n≤2×10^​5,1≤k≤10^9)n,k(1≤n≤2×10​5,1≤k≤109)。 第二行 ...

    7-4 中位数 (10分)

    一个有 n 个整数的数组 a,n是一个奇数。
    每次可以选择数组里的一个元素 aia_{i} 并把这个元素加上 1。
    在至多 kk 次操作之后,数组的中位数最大能变成多少。

    输入格式:

    多组输入
    第一行两个整数 n,k(1n2×105,1k109)n,k(1≤n≤2×10^5,1≤k≤10^9)
    第二行 nn 和整数 a1,a2,......,ana_1,a_2,......,a_n

    输出格式:

    kk 次操作后数组的中位数。
    输入样例:

    3 2
    1 3 5
    

    输出样例:

    5
    

    解题思路

    假设原数组的中位数为 A[mid] 则按照题目要求进行k次操作后中位数应该在A[mid]A[mid]+k之间,在这个区间内使用二分法便可以搜索出满足条件且最大的中位数。

    避雷

    1. 测试数据有多组
    2. 需使用long long类型

    AC代码

    #include <iostream>
    #include <algorithm>
    #define ll long long
    using namespace std;
    
    /**
     * 中位数变为 mid 需要的操作次数
     * @param arr 有序数组
     * @param len 数组长度
     * @param mid 预期中位数
     * @return 操作次数(每次操作挑一个元素加1)
     */
    ll time(const ll *arr, ll len, ll mid) {
        ll t = 0;
        for (ll i = len/2; i < len; ++i) {
            if(arr[i] < mid) t += mid - arr[i];
            else break;
        }
        return t;
    }
    
    int main() {
        ll n, k;
        while (cin >> n >> k) {
            auto *arr = new ll[n];
            for (ll i = 0; i < n; ++i) cin >> arr[i];
            sort(arr, arr + n);
            // k次操作后中位数肯定介于arr[n/2]和arr[n/2]+k之间
            // 在此区间二分法搜寻结果
            ll l = arr[n/2];
            ll r = arr[n/2]+k;
            while (l <= r) {
                ll mid = (l + r) / 2;
                if (time(arr, n, mid) <= k) l = mid + 1;
                else r = mid - 1;
            }
            cout << l-1 << endl;
        }
        return 0;
    }
    
    展开全文
  • 或者求个整数m和n需要改变m二进制中的多少位才能得到n,可以先做 m^n 异或运算,然后求这个数中多少个1。 面试题11:数值整数次方:如果采用常规解法,需要注意地方:当指数为负数时候;当底数为零且指数...
  • 得到单元格编号组中最大的数或最小的 标记出3个最大最小值 取前五名,后五名的方法 如何用公式求出最大值所在的行? 求多个最高分 如何求多条件的平均值 想求出第三大之数值 【查询和查找引用】 查找顺序公式 怎样...
  • 兔子问题、素数、水仙花、正整数分解质因数、成绩等级划分、最大公约数和最小公倍数、统计字符串字母、空格、数字和其它字符个数、s=a+aa+aaa+aaaa+aa...a、完数、球反弹、有1、2、3、4个数字,能组成多少个...
  • EXCEL函数公式集

    热门讨论 2010-03-16 03:26:38
    得到单元格编号组中最大的数或最小的 标记出3个最大最小值 取前五名,后五名的方法 如何用公式求出最大值所在的行? 求多个最高分 如何求多条件的平均值 想求出第三大之数值 【查询和查找引用】 查找顺序公式 怎样...
  • 2.5.2 某公司申请到一个C类IP地址,但要连接6个的子公司,最大的一个子公司有 26台计算机,每个子公司一个网段,则子网掩码应设为? 2.5.3 与10.110.12.29mask 255.255.255.224属于同一网段的主机IP地址? ...
  • 每个人到来时看到数是多少条? (28)约瑟夫环问题:编号为1,2,3,...,nn个人按顺时针方向围坐一圈,每人持有一个正整数密码。一开始任选一个正整数m作为报上限值,从第一个人开始按顺时针报,报到m时停止...
  • 9.8将一个5×5的矩阵中最大的元素放在中心,4个角分别放在4个最小的元素(按从左到右,从上到下的顺序,依次从小到大存放),写一个函数实现之,并用main函数调用。 78 10.9主函数中输入10个等长的字符串。用另一...
  • javascript入门笔记

    2018-05-15 15:01:07
    Javascript,简称为 JS,一款能够运行 JS解释器/引擎 中的脚本语言 JS解释器/引擎 JS运行环境: 1、独立安装JS解释器 - NodeJS 2、嵌入浏览器中的JS解释器 JS发展史: 1、1992年 Nombas 开发...
  • java 经典习题.doc

    2009-09-16 11:32:59
    题目:打印出所有"水仙花数",所谓"水仙花数"指一个三位数,其各位数字立方和等于该数本身。例如:153一个"水仙花数",因为153=1三次方+5三次方+3三次方。 1.程序分析:利用for循环控制100-999个数,...
  • 题目: 有1、2、3、4个数字,能组成多少个互不相同且无重复数字位数?都是多少? 【程序2】 题目:企业发放奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高  于10万元,低于20万元时,...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    6.数据结构评价算法的两个重要指标(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构研讨数据_(1)物理结构_和_(2)逻辑结构 _,以及它们之间相互关系,并对与这种结构定义...
  • 个平方三位数获得三个平方二位数 24.阿姆斯特朗数 25.完全数 26.亲密数 27.自守数 28.回文数 29.求具有abcd=(ab+cd)2性质四位数 30.求素数 <br>C/C++语言经典实用趣味程序...
  • 个平方三位数获得三个平方二位数 24.阿姆斯特朗数 25.完全数 26.亲密数 27.自守数 28.回文数 29.求具有abcd=(ab+cd)2性质四位数 30.求素数 <br>C/C++语言经典实用趣味程序...
  • Java范例开发大全 (源程序)

    热门讨论 2011-04-27 07:47:22
     实例30 求最大的随机数 44  3.5 switch语句 45  实例31 判断字母分类 46  实例32 优良及差 47  实例33 打印任意一年日历 48  实例34 一年四季的划分 51  第2篇 Java数据处理  第4章 异常处理(教学...
  • java范例开发大全源代码

    热门讨论 2011-10-30 23:31:51
     实例30 求最大的随机数 44  3.5 switch语句 45  实例31 判断字母分类 46  实例32 优良及差 47  实例33 打印任意一年日历 48  实例34 一年四季的划分 51  第2篇 Java数据处理  第4章 异常处理...
  • java范例开发大全

    2013-03-08 20:06:54
    实例30 求最大的随机数 44 3.5 switch语句 45 实例31 判断字母分类 46 实例32 优良及差 47 实例33 打印任意一年日历 48 实例34 一年四季的划分 51 第2篇 Java数据处理 第4章 异常处理(教学视频:62分钟) 54 4.1 ...
  • 世界500强面试题.pdf

    2019-11-01 14:33:26
    1.4.5. 求一个矩阵中最大的二维矩阵(元素和最大) ........................................ 86 1.4.6. 强大的和谐 ........................................................................................ 90 ...
  • Java范例开发大全(全书源程序)

    热门讨论 2013-04-05 11:50:26
    实例30 求最大的随机数 44 3.5 switch语句 45 实例31 判断字母分类 46 实例32 优良及差 47 实例33 打印任意一年日历 48 实例34 一年四季的划分 51 第2篇 Java数据处理 第4章 异常处理(教学视频:62分钟) ...
  • 用例7:计算个月之间相差天数(DATEVALUE) 源文件:光盘\源文件\04\07.xlsx 用例8:统计某月第四周收入金额(WEEKNUM) 源文件:光盘\源文件\04\025.xlsx 用例9:安排会议时间(TIME) 源文件:光盘\...
  • 如果将一个 16 二进赋给一个 8 位的字节变量,则自动截断为低 8 ,而丢掉高 8 。 ++var 表示对变量 var 先增一;var—表示对变量后减一。 x |= 0x0f;表示为 x = x | 0x0f; 高四。 6. While( 1 ); 表示...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

在两位数中最大的奇数是多少