牛客编程巅峰赛S2第1场 - 青铜&白银&黄金
最小差值
https://ac.nowcoder.com/acm/contest/9004/A
A 最小差值
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求最小差值
* @param a int整型vector 数组a
* @return int整型
*/
int minDifference(vector<int>& a) {
// write code here
vector<int>b;
for(int i=0;i<a.size();++i)
b.push_back(a[i]);
int n=a.size();
long long ans=INT_MAX;
sort(b.begin(),b.begin()+n,less<int>());
for(int i=1;i<n;++i){
ans=min(ans,1LL*abs(1LL*b[i]-1LL*b[i-1]));
}
return (int)ans;
}
};
B Tree IV
解题思路：最后一层前面的是满二叉树，由满二叉树的结构可以发现，最左边的结点都是上一层最左边的结点的2倍，而且每层结点j的个数和最左边的结点数值相同，由于每层结点数值连续，则可以用s=(i+2*i-1)*i/2%mod;求出每层的结点数之和，注意要先除2再取余，否则可能会改变精度导致答案错误，节点数和乘上各层深度相加再取余，再将最后一层的结点数求出并乘上深度相加取余即可。class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n long长整型 表示标准完全二叉树的结点个数
* @return long长整型
*/
long long tree4(long long n) {
// write code here
long long mod=998244353,i,res=0,dep=1,s;
for(i=1;i*2<=n;i*=2)//只看最左边的结点
{
s=(i+2*i-1)*i/2%mod;
res=(res+s*dep)%mod;
dep++;
}
s=(i+n)*(n-i+1)/2%mod;//最后一层
res=(res+s*dep)%mod;
return res;
}
}; C 牛牛组数
解题思路：首先写几个例子可以看出：
k=1时字符从大到小排列即可；k>=2时留下k-1个数(数字字符中相对较小的)作为个位数，剩下的字符按数字字符从大到小组成一个最大的数，那么这样求得的和最大（每个数字字符都要全部用完）；
注意转换为字符串输出前需要在最后加上'\0'
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回最大和的字符串
* @param x string字符串 即题目描述中所给字符串
* @param k int整型 即题目描述中所给的k
* @return string字符串
*/
int tong[10],a[100010]={0};
string Maxsumforknumers(string x, int k) {
// write code here
for(int i=0;i<x.size();++i)
tong[x[i]-'0']++;
int f=9,i;//将k个数字分成k-1个个位数和一个x.size()-k+1位的数
for(i=x.size()-k;i>=0;--i)
{
while(!tong[f])f--;//找到存在的最大数
a[i]=f;
tong[f]--;//使用了一个f
}
for(;f>0;f--)//处理剩下未使用的字符
{
a[0]+=f*tong[f];//将剩下充当个位数的先加在a[0]位上
}
for(i=0;i<x.size();i++)
{
a[i+1]+=a[i]/10;
a[i]=a[i]%10;//将刚才加上去的个位数超过10的部分分到高位上
}
for(i=x.size();i>=0;--i)//可能有进位到第x.size()位的
if(a[i]!=0)break;//找到第一位不是0的位数
string s="";//将得到的数转换为string类型输出
for(;i>=0;--i)s+=a[i]+'0';
s+='\0';
return s;
}
}; 
哔哩哔哩公司氛围 96人发布
