- 浏览: 120728 次
- 性别:
- 来自: 北京
最新评论
写了两三个版本,最后这个效率最高
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl #define MP(X,Y) make_pair(X,Y) using namespace std; typedef long long LL; typedef pair<int, int> pr; int T, n; vector<pr> dev[105], allw; int idx[105]; int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); allw.clear(); for (int i = 0; i < n; ++i) { int mi; scanf("%d", &mi); dev[i].resize(mi); for (int j = 0; j < mi; ++j) { scanf("%d%d", &dev[i][j].first, &dev[i][j].second); allw.push_back(MP(dev[i][j].first, i)); } sort(dev[i].begin(), dev[i].end()); for (int j = mi - 2; j >= 0; --j) dev[i][j].second = min(dev[i][j].second, dev[i][j + 1].second); idx[i] = 0; } sort(allw.begin(), allw.end()); int cost = 0; for (int j = 0; j < n; ++j) cost += dev[j][0].second; double ans = (double)allw[0].first / cost; for (int i = 1; i < allw.size(); ++i) { int row = allw[i - 1].second; cost -= dev[row][idx[row]].second; if (idx[row] + 1 == dev[row].size()) break; cost += dev[row][++idx[row]].second; ans = max(ans, (double)allw[i].first / cost); } printf("%.3f\n", ans); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1189/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 867线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 890线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 944写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 1012转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1223封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 829终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
布斯(Booth)乘法
2010-10-07 19:59 1175源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 838import java.util.*; import j ... -
整数划分
2010-10-07 10:38 861#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 1011// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1073typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1170最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1339Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 811static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 921标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 881“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1079“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1030推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ... -
RMQ模板
2010-07-28 11:04 1224/* * Author: rush * Creat ...
相关推荐
【标题】"pku.zip_PKU" 指的是一份与北京大学(Peking University, PKU)相关的压缩文件。从描述来看,这份压缩包包含了部分编程题目的代码,可能是学生或者爱好者在解决北京大学编程竞赛或课程作业时编写的。"pku"这...
"pku经典题目解题报告"这一标题揭示了文件内容的核心,它表明这是一份关于北京大学(PKU)编程竞赛或算法竞赛中的经典问题的解答集。通常,这样的报告会涵盖一系列在PKU历年比赛中出现的难题,包含了解题思路、算法...
pku1000 pku1000程序 解题报告
在编程竞赛的世界里,北京大学(PKU)的ACM团队以其高质量的题目和独特的解题思路闻名。"PKU-ACM.rar"这个压缩包包含了北大ACM题目的一些核心知识点,旨在帮助参赛者理解和掌握算法竞赛中的生命周期题目解法。本文将...
benchmark (PKU-MMD) for continuous multi-modality 3D human action understanding and cover a wide range of complex human activities with well annotated information. PKU-MMD contains 1076 long video ...
【标题】"ACM代码 之pku代码" 涉及的是在计算机科学领域中的算法竞赛编程,尤其是北京大学(Peking University, PKU)的ACM/ICPC(国际大学生程序设计竞赛)训练代码。这些代码是参赛者或教练为了准备这类竞赛而编写的,...
标题 "pku acm 一些代码" 暗示了这是一个与北京大学(Peking University, 简称PKU)的ACM(国际大学生程序设计竞赛)相关的代码集合。在这个领域,参赛者通常需要解决算法问题,编写高效且优化的代码来求解数学、逻辑...
标题"Pku1664"很可能是指北京大学(Peking University)在某个编程竞赛或课程中的一道题目或项目,编号为1664。这道题目可能涉及到计算机科学的基础概念,尤其是算法和数据结构。描述中提到的是"Pku1664源代码",暗示...
8数码代码pku1077,300ms(哈希+广度搜索)
标题中的“pku1742.rar_pku 17_pku 1742 _报告及程序”表明这是一个与北京大学(Peking University, 简称PKU)相关的项目,项目编号可能是1742,内容包括了结题报告和程序代码。这个压缩包很可能是学生或研究人员提交...
标签部分进一步细化了内容:"pku acm_pku"再次强调这是北京大学ACM竞赛的资料,"pku__1709__crossword"可能是特定的题目标签,而"pku_acm"可能是北京大学ACM团队的标识。"visual_c"可能表示这些代码是使用C++语言,...
"p_acm"、"pku_acm"以及"pu_acm.pku_pku"等标签可能是用于分类或标识这些代码属于北京大学(Peking University, PKU)的ACM训练题目。"acm"一词重复出现,进一步强调了这是关于ACM编程竞赛的内容。 描述中提到"acmer...
PKU 2339 Rock, Scissors, Paper 源代码
标题中的“pku1088.rar_pku 10_pku 1088_poj 1088”指的是北京大学(Peking University, PKU)编程竞赛中的第1088题,也称为POJ(Peking University Online Judge)的1088题。这个题目在编程竞赛社区中通常有一个特定的...
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
分词训练用的pku训练集,主要是说明相似度计算的样例数据。
北京大学pku2317 Questions and answers c++标程 文件名为2371.cpp
北京大学(PKU)作为国内顶尖的学府,其提供的“pku离线题库”就是这样的一个宝贵资源,它不仅支持离线使用,还允许用户在没有网络时仍然能够有效地进行题目的查阅与练习。 “pku离线题库”这个资源的设计初衷,...