蓝桥杯练习017

第几个幸运数字

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

到 X 星球旅行的游客都被发给一个整数，作为游客编号。

X 星的国王有个怪癖，他只喜欢数字 3,5 和 7。

国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。

我们来看前 10个幸运数字是：

3579152125273545

因而第 11个幸运数字是： 49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505 是第几个幸运数字。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

暴力搜索

#include<iostream>
using namespace std;

int main()
{
    
	long long n=59084709587505;
	int ans=0;
	for(long long i=1;i<=n;i*=3){
    
		for(long long j=1;i*j<=n;j*=5){
    
			for(long long k=1;i*j*k<=n;k*=7){
    
				ans++;
			}
		}
	}
	cout<<ans-1<<endl;
	return 0;
}

优先队列+去重

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef priority_queue<ll,vector<ll>,greater<ll> > pq;
typedef map<ll,int> mp;
mp vis;
int sum[5]={
    3,5,7};
int main(){
    
   ll tem=59084709587505;
 
    pq qu;
    qu.push(1);
    int ans=0;
    while(1){
    
        ll cnt=qu.top();
        qu.pop();
        if(cnt==tem){
    
           cout<<ans<<endl;
           break;
        }
        ll temcnt;
        for(int i=0;i<3;i++){
    
            temcnt=cnt*sum[i];
            if(vis[temcnt]==0){
    
                qu.push(temcnt);
                vis[temcnt]=1;
            }
        }
        ans++;
    }
}

set+upper_bound

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
set<LL> se; 
int main(){
    
    LL f = 1;
    LL a[3] = {
    3,5,7};
    while(1){
    
        for(int i=0;i<3;i++)
            if(f*a[i]<=59084709587505) 
                se.insert(f*a[i]);
        f = *se.upper_bound(f);
        if(f>=59084709587505) 
            break;
    }
    cout<<se.size(); 
    return 0;
}

付账问题

题目描述

几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。

现在有 n 个人出去吃饭，他们总共消费了 S元。其中第 i 个人带了 ai元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的"偏差有多大"。形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

输入描述

第一行包含两个整数 n、S；

第二行包含 n 个非负整数 a1, ⋯, an。

其中，n≤5×10^5, 0≤ai≤10^9 。

输出描述

输出最小的标准差，四舍五入保留 4 位小数。

保证正确答案在加上或减去 10^(−9)后不会导致四舍五入的结果发生变化。

输入输出样例

示例

输入

5 2333
666 666 666 666 666

输出

0.0000

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

思路

贪心法：

1. 准备贪心：先将花费数组从小到大排序
2. 贪心策略：
   1. 从数组最小的元素开始，每次做判断
   2. 若当前元素小于剩余花费平均值，则取该元素不改变值，将平均成本转嫁到后续元素上
   3. 若当前元素大于等于剩余花费平均值，则后续元素也大于该平均值，能够承接前较小元素的成 本，将当前元素之后的所有元素取剩余花费平均值
3. 结束贪心，解出标准差

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
using namespace std;

int main()
{
    
	int n;
	double S;
	double sum=0;
	cin>>n>>S;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	double arg=1.0*S/n;
	double newarg=arg;
	sort(a,a+n);  
	for(int i=0;i<n;i++){
    
		newarg=S/(n-i);
		if(a[i]<newarg){
    
			sum=sum+(a[i]-arg)*(a[i]-arg);
			S=S-a[i];
		}else{
    
			sum=sum+(newarg-arg)*(newarg-arg)*(n-i);
			break;
		}
			
	}
	printf("%.4lf",sqrt(sum/n));
	return 0;
}