第七次周练(1007,1008)
1007 求期望
思路：对于每一种器材有两种选择，1/2的概率，根据乘法原理
1/(2^2)(a+b)(c+d) = 1/(2^2) (ac+ad+bc+bd) 可知等式右边就是所求的期望，可以合并成等式左边的式子，所有只要对每种器材的两个属性求和然后相乘取模，又因为最后结果要先乘2^n,所以最后的答案就是(a1+b1)(a2+b2)...(an+bn)
#include <bits/stdc++.h>
#define ll long long
const int mod = 1e9+7;
using namespace std;
int a[1005],b[1005],dp[1005][2],n;
ll sum = 0;
int main()
{
//freopen("test1007.In","r",stdin);
//freopen("test1007.Out","w",stdout);
while(cin >> n){
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
ll ans = 1;
for(int i = 1; i <= n; i++){
ans = (ans % mod * 1ll*(a[i] + b[i]) % mod) % mod;
}
cout << (ans) % mod << endl;
}
return 0;
} 1008 分组
思路：
简单排序，分k组，因为要保证相减后得到的值最大，所有考虑优先考虑两两一组，最大和最小的一组，次大和次小的一组，直至分完k组。
如果2*k <=n，可能有几组不止两人，但不影响结果，如果2*k>n, 那么就会有一个人一组的情况。
综合起来看用前k大的和减去前k小的和就是答案。
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
//freopen("test.In","r",stdin);
//freopen("test.Out","w",stdout);
int n,k;
while(cin >> n >> k){
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a+1,a+n+1);
long long sum = 0;
int i = 1,j = n;
for(int i = n; i >= n-k+1; i--){
sum += a[i];
}
for(int i = 1; i <= k; i++){
sum -= a[i];
}
cout << sum << endl;
}
return 0;
} 
查看40道真题和解析
投递腾讯等公司10个岗位 >