429c Leha and Function
2024-10-21 19:43:03
题目
解题报告
F(n, k)
是在集合{1, 2, 3, ..., n}
中所有的具有k
个元素的子集中分别取最小值,相加后的期望。
例如:要求F(4, 2)
,根据定义有{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
,则F(4, 2)=(1+1+1+2+2+3)/6=1.6666666666666...
对于F(n, k)
,我们有这么一个结论,
$$ F(n, k) > F(m, k), n > m $$
$$F(n, k) > F(n, q), k < q $$
因此,原问题变为将A按照由大到小排序后,求B数组每个元素在排序后的编号,在此位置输出排序后的Ai
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
#define REP(i, k, n) for (int i = k; i < n; i++)
#define REPP(i, k, n) for (int i = k; i <= n; i++)
const int inf = 0x3f3f3f3f;
#define LOCAL
int a[200005], h[200005];
pair<int, int> b[200005];
bool cmp(int a, int b)
{
return a > b;
}
bool cmp1(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
int main(int argc, char * argv[])
{
#ifdef LOCAL
freopen("/Users/huangjiaming/Documents/Algorithm/oj/data.in", "r", stdin);
//freopen("/Users/huangjiaming/Documents/Algorithm/oj/data.out", "w", stdout);
#endif
int n;
while (~scanf("%d", &n))
{
REPP(i, 1, n)
scanf("%d", a+i);
REPP(i, 1, n)
{
scanf("%d", &b[i].first);
b[i].second = i;
}
sort(a+1, a+n+1, cmp);
sort(b+1, b+n+1, cmp1);
REPP(i, 1, n)
h[b[i].second] = i;
REPP(i, 1, n)
printf("%d ", a[h[i]]);
printf("\n");
}
return 0;
}
最新文章
- 黑马程序员-autorelease pool
- Java Hotspot G1 GC的一些关键技术
- iOS-UICollectionView的简单使用(原创)
- vb.net三层实现登录例子
- HDU 4627 E(Contest #3)
- Python 多线程学习(转)
- darwin转发时,摄像机在3G和4G模式下的参数设置
- ThinkPHP CURD方法盘点:field方法
- 重温Java的类加载机制
- Amazon AWS创建RHEL 7实例
- 关于【IE兼容】的都在这
- NOIP2010-普及组复赛-第二题-接水问题
- Linux系统fdisk分区
- vmware虚拟机各个版本的安装破解(附安装包和注册机)
- Linux - sed 工具
- 技术分享:RxJS实战练习-经典游戏Breakout
- Metasploit 简单渗透应用
- mysql系列十一、mysql优化笔记:表设计、sql优化、配置优化
- 关于repaint和reflow的笔记
- GS 服务器端开启webservice 远程调试的方法