欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客编程巅峰赛S1第8场 - 青铜&白银 A.数学B.贪心C.枚举

程序员文章站 2022-03-23 11:17:25
链接:https://ac.nowcoder.com/acm/contest/6776/A来源:牛客网题目描述牛牛有一个边长为1的正六边形,只要牛牛一推它就可以一直滚下去,正六边形左下角为A,牛牛想知道正六边形翻滚k次A点的轨迹边长是多少呢。如图是正六边形翻滚一次的情况。给定正六边形翻滚次数k,求A点翻滚轨迹长度示例1输入复制3输出复制4.955392备注:1\leq k\le10^31≤k≤103,返回值与答案误差应小于0.00001class Solution {publ...

链接:https://ac.nowcoder.com/acm/contest/6776/A
来源:牛客网

题目描述
牛牛有一个边长为1的正六边形,只要牛牛一推它就可以一直滚下去,正六边形左下角为A,牛牛想知道正六边形翻滚k次A点的轨迹边长是多少呢。如图是正六边形翻滚一次的情况。给定正六边形翻滚次数k,求A点翻滚轨迹长度

示例1
输入
复制
3
输出
复制
4.955392
备注:
1\leq k\le10^31≤k≤10
3
,返回值与答案误差应小于0.00001

class Solution {
public:
    /**
     * 
     * @param k int整型 翻滚次数
     * @return double浮点型
     */
    double circumference(int k) {
        // write code here
        double ans=0;
        double d[]={0,2,2*sqrt(3),4,2*sqrt(3),2};
        for(int i=1;i<=k;i++){
            ans+=d[i%6];
        }
        return ans*acos(-1)/6.0;
    }
};

链接:https://ac.nowcoder.com/acm/contest/6776/B
来源:牛客网

题目描述
在牛牛面前有nn个瓶子,每个瓶子的大小体积都一样,但是每个瓶子内的含水量都不相同。
因为牛牛是个完美主义者,他希望瓶子中的水能够满足他的要求,他的要求是瓶子中的水最少为xx。所以他打算对这些瓶子里的水进行重新分配,以满足最多的瓶子中水量大于等于xx。
牛牛的分配规则是:每次可以选择多个瓶子,将里面的水平均分配到已选择的瓶子中。
给定nn个瓶子和牛牛的对瓶中的水量要求xx,以及nn个瓶子中的含水量,求最多可以有多少个瓶子满足牛牛的要求?

示例1
输入
复制
3,7,[9,4,9]
输出
复制
3
说明
一共有3瓶水,容量分别为9 4 9,牛牛希望每瓶水中最少容量为7。所以可以选择这3瓶水,平均分配后每瓶水的含量都大于7,所以满足牛牛要求的瓶子最多的数量为3。
示例2
输入
复制
2,5,[4,3]
输出
复制
0
说明
一共有2瓶水,但是每瓶水的容量都无法满足牛牛的要求,所以即使不管怎么分配,也无法满足牛牛的要求。
备注:
1 \leq n \leq 10^{6},代表瓶子的数量1≤n≤10
6
,代表瓶子的数量
1 \leq x \leq 10^{9},代表牛牛的对瓶中的水量要求1≤x≤10
9
,代表牛牛的对瓶中的水量要求
a)代表每个瓶子中的含水量a1,a2,a3 …an (1≤ai ≤1e9)代表每个瓶子中的含水量
对于25%的数据,1 \leq n \leq 10^{2},1 \leq x,a_{i} \leq 10^{3}对于25%的数据,1≤n≤10
2
,1≤x,a
i

≤10
3

对于75%的数据,1 \leq n \leq 10^{4},1 \leq x,a_{i} \leq 10^{6}对于75%的数据,1≤n≤10
4
,1≤x,a
i

≤10
6

对于100%的数据,1 \leq n \leq 10^{6},1 \leq x,a_{i} \leq 10^{9}对于100%的数据,1≤n≤10
6
,1≤x,ai ≤1e9

class Solution {
public:
    /**
     * 返回重新分配后,满足牛牛要求的水量的瓶子最多的数量
     * @param n int整型 瓶子的数量
     * @param x int整型 牛牛的对瓶中的水量要求
     * @param a int整型vector 每个瓶子中的含水量
     * @return int整型
     */
    typedef long long ll;
    int solve(int n, int x, vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
      ll  sum=0,ans=0;
        for(int i=n-1;i>=0;i--){
              sum+=a[i];
            if(sum>=1ll*x*(ans+1)){
                ans++;
            }
            else break;
        }
        return ans;
        
    }
};

链接:https://ac.nowcoder.com/acm/contest/6776/C
来源:牛客网

题目描述
牛牛和牛妹在玩一个游戏,在他们面前有n个数,他们对每个数可以进行 +1 或 -1 操作,但对于每一个数,该操作最多只能执行一次。
游戏胜利的目标是:使用最少的操作次数,将这几个数构造成一个等差数列。
牛牛特别想赢得游戏,所以他想让你帮他写一个程序,得出最少多少次操作后能使这几个数变成一个等差数列,当然,如果完全不能构造成功,就输出-1。
示例1
输入
复制
4,[24,21,14,10]
输出
复制
3
说明
在第一个例子中,牛牛应该对第一个数字+1,对第二个数字-1,对第三个数字+1,而第四个数字应该保持不变。最后,序列就变成了[25,20,15,10],这是一个等差数列且操作次数最少。
示例2
输入
复制
3,[14,5,1]
输出
复制
-1
说明
在第二个例子中,不可能只对其中的数字最多操作一次就得到等差数列。
备注:
1\leq n \leq10^{5},代表有n个数1≤n≤10
5
,代表有n个数
b_{1},b_{2},…b_{n} (1\leq b_{i} \leq10^{9}),代表这n个数字的大小b
1

,b
2

,…b
n

(1≤b
i

≤10
9
),代表这n个数字的大小
对于20%的数据,1\leq n \leq10, 1\leq b_{i} \leq10^{3}对于20%的数据,1≤n≤10,1≤b
i

≤10
3

对于60%的数据,1\leq n \leq10^{3}, 1\leq b_{i} \leq10^{6}对于60%的数据,1≤n≤10
3
,1≤b
i

≤10
6

对于100%的数据,1\leq n \leq10^{5}, 1\leq b_{i} \leq10^{9}对于100%的数据,1≤n≤10
5
,1≤b
i

≤10
9

class Solution {
public:
    /**
     * 返回最少多少次操作后能使这几个数变成一个等差数列,如果完全不能构造成功,就返回-1
     * @param n int整型 代表一共有n个数字
     * @param b int整型vector 代表这n个数字的大小
     * @return int整型
     */
    int solve(int n, vector<int>& b) {
        // write code here
       int ans=0x7f7f7f7f;
        if(n<=2)return 0;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                int fir=b[0]+i;
                int sec=b[1]+j;
                int d=fir-sec;
                int cnt=abs(i)+abs(j);
                int cur=sec;
              for(int k=2;k<n;k++){
                  cur-=d;
                  if(abs(cur-b[k])<=1){
                      cnt+=abs(cur-b[k]);
                  }
                  else break;
                  if(k==n-1){
                      ans=min(ans,cnt);
                  }
              }
            }
        }
        if(ans==0x7f7f7f7f)return -1;
        return ans;
    }
};

本文地址:https://blog.csdn.net/Gyibin/article/details/107883688

相关标签: 牛客