美团笔试 3.26 C++ 一些疑惑的地方
第二题 求圆环面积
我用的C++，对半径排序了，也用了<math>里面的M_PI,但是还是只有18%，有没有大佬帮忙看一下。
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
int n=0;
cin>>n;
vector<long> redis(n,0);
for(int i=0; i<n; i++){
cin>>redis[i];
}
if(n<=0){
cout<<0<<endl;
return 0;
}
if(n==1){
double tmp = M_PI*redis[0]*redis[0];
cout<<fixed<< setprecision(5)<<tmp<<endl;
return 0;
}
sort(redis.begin(),redis.end());
long sum=0;
for(int i=0; i<n-1; i=i+2){
sum = sum + (redis[i] + redis[i+1])*(redis[i]-redis[i+1]);
}
if(n&0x1==1){
sum+=redis[n-1]*redis[n-1];
}
double ans = M_PI*sum;
cout<<fixed<< setprecision(5)<<ans<<endl;
return 0;
}
第三题 用的是线性DP，但是会TLE，感觉第二个循环里面可以做优化，尝试了做了一个剪枝，没有来得及做步长的优化，又有大佬分享一下经验
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;
#define MAGIC 998244353
int main(){
int n=0;
cin>>n;
vector<int>num(n);
for(int i=0;i<n;i++){
cin>>num[i];
}
vector<int> dp(n,0);
dp[0]=1;
for(int i=1; i<n; i++){
int step=1;
int first=true;
for(int j=0; j<=i; j=j+step){
if((j+1)>(num[i]+1)/2) break;
if(num[i]%(j+1)==0){
if(j==0){
dp[j] = dp[j]+1;
}else{
dp[j] = dp[j]+dp[j-1];
}
if(first && (j+1) !=1){
step = j+1;
}
}
}
}
int res=0;
for(int i=0; i<n; i++){
res = (res+dp[i])%MAGIC;
}
cout<<res<<endl;
}
美的集团公司福利 724人发布
