京东春招0407编程题参考代码汇总

拍卖：

排序以后枚举答案

示例代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 1009
int a[maxn];
int main(){
	int n, m, ans=0, a0;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++) scanf("%d", &a[i]);
	sort(a+1, a+1+m);
	for(int i=1; i<=m; i++) if (ans < a[i]*min(n,m-i+1))
		ans=a[i]*min(n,m-i+1), a0=a[i];
	printf("%d\n", a0);
	return 0;
}

通过考试：

概率dp，定义状态前i个题目对j个的概率，递推求解

示例代码：

#include <bits/stdc++.h>
#define maxn 109
using namespace std;
int n,a[maxn];
double dp[maxn][maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0]=dp[i-1][0]*(100.0-a[i])/100;
		for(int j=1;j<=i;j++)
			dp[i][j]=dp[i-1][j]*(100.0-a[i])/100+dp[i-1][j-1]*1.0*a[i]/100;
	}
	int low=(3*n+4)/5;
	double ans=0;
	for(int i=low;i<=n;i++)
		ans+=dp[n][i];
	printf("%.5f\n",ans);
	//system("pause");
	return 0;
}

分堆：

找规律，可以证明k,k+1,k,k+1...为最优序列

示例代码：

#include <cstdio>
#define maxn 109
using namespace std;
int main(){
	int n, k, ans;
	scanf("%d%d",&n, &k);
	ans = n / (2 * k + 1);
	ans *= 2;
	if(n % (2 * k + 1) >= k)
		ans++;
	printf("%d\n",ans);
	//system("pause");
	return 0;
}

站队：

找到所有警察的位置，标记被警察看到的位置

示例代码：

#include <bits/stdc++.h>
#define maxn 100009
using namespace std;
int n;
char s[maxn];
bool vis[maxn];
int main(){
    scanf("%d", &n);
    scanf("%s", s);
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n; i++){
        if(s[i] == 'X' || s[i] == '#')
            continue;
        int x = s[i] - '0';
        for(int j = 0; j <= x; j++){
            if(i - j >= 0)
                vis[i - j] = 1;
            if(i + j < n)
                vis[i + j] = 1;
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'X' && vis[i])
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

异或：

模拟二进制运算，之后转成十进制输出

示例代码：

#include<bits/stdc++.h>
using namespace std;
char s[100];
int getnum(int n){
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans *= 2;
        ans += s[i] - '0';
    }
    return ans;
}
int main(){
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    int a = getnum(n);
    scanf("%s", s);
    int b = getnum(n);
    printf("%d\n", a ^ b);
    return 0;
}

终结者C：

运输车相对位置不变，看成运输车不动，激光炮动，枚举放激光炮的地方

示例代码：

#include<cstdio>
#include<cstring>
int a[205],b[205],c[205];
bool q(int w,int e){
	return a[e]<=a[w]&&b[e]>=a[w];
}
int n;
int s(int w,int e){
	int re=0;
	for(int i=1;i<=n;i++)
		if(q(w,i)||q(e,i))re++;
	return re;
}
void work(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l;
		scanf("%d %d",&a[i],&l);
		b[i]=a[i]+l;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
				int k=s(i,j);
				if(k>ans)ans=k;
			}
	printf("%d\n",ans); 
} 
int main(){ 
	work(); 
	return 0;
}