首页 > 其他分享 >鲁的智力 题解

鲁的智力 题解

时间:2024-10-06 13:23:04浏览次数:8  
标签:dots 学科 int 题解 智力 Delta 排名

题意

有 \(n\) 个人,\(m\) 个学科,你第 \(i\) 门学科排在第 \(a_i\) 名,且每个人在每个学科得到的分数是一个 \(0\) 到 \(1\) 之间的一个实数,求你总分排名的最大、小值。

题解

先考虑排名最高的情况。

我们可以每一科都这样构造:

\[b_1 = 1 \]

\[b_2 = 1 - \Delta x \]

\[b_3 = 1 - 2\Delta x \]

\[\dots \]

\[b_k = 1 - (k - 1)\Delta x \]

\[b_{k + 1} = 0 + (n - k)\Delta x \]

\[b_{k + 2} = 0 + (n - k - 1)\Delta x \]

\[\dots \]

\[b_n = 0 \]

其中 \(k\) 为你的排名、\(b_i\) 为第 \(i\) 名的分数、\(\Delta x\) 是一个极小值。

这样可以使得有任意一科在你下面的都会被你超越,此时你排名最高。

最低同理。

namespace zqh {
int n, m;

void init() {
    cin >> n >> m;
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
        int s;
        cin >> s;
        x += s - 1;
        y += m - s;
    }
    cout << max(1LL, m - y) << "\n" << min(m, x + 1);
}

void solve() {}

void main() {
    init();
    solve();
}
}  // namespace zqh

标签:dots,学科,int,题解,智力,Delta,排名
From: https://www.cnblogs.com/zphh/p/18449015

相关文章

  • 游览计划 题解
    题意给定一张无向图,选取四个点\(a\neb\nec\ned\),求\(f(a,b)+f(b,c)+f(c,d)\)的最大值,其中\(f(u,v)\)表示点\(u\)到点\(v\)的最短路长度。题解如果顺着枚举四个点\(a\)、\(b\)、\(c\)、\(d\),是一个\(n^4\)的复杂度,显然过不了。但是我们发现如果确定......
  • 洛谷 P3523 题解
    洛谷P3523[POI2011]DYN-Dynamite分析二分答案,问题转化为:对于给定的\(K\),选择尽可能少的节点,使得所有关键节点都被「覆盖」。对于一个关键节点,「覆盖」的定义为:存在一个被选择的点与这个关键节点的距离不大于\(K\)。方便起见,我们指定\(1\)号节点是这棵树的根节点。我们......
  • [题解]ABC374 A~E
    A-Takahashisan2直接判断字符串是否以san结尾即可。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ strings; cin>>s; intn=s.size(); if(s[n-1]=='n'&&s[n-2]=='a'&&s[n-3]=='s')cout<<&......
  • P11059 [入门赛 #27] 数字 (Hard Ver.)题解
    Solution先读题:在给定x的位数\(n\)和模数\(p\)后,要求构造一个\(x\)在满足\(x\modp\)的余数尽可能小的前提下使\(x\)的数字尽可能小。我们假设\(x\)的各位数字之和为\(m\),有\(1\lem\le9n\)。.(当\(x\)仅在最高位有1时\(m=1\),称为情况一,当x每位为9时\(m=9n\),称为情况二......
  • ABC374E 题解
    好题。爱做。标签:二分。求最大的最小值,考虑二分答案。然后问题就转化成了(求\(n\)次):有两种物品,每种物品有一个代价和价值,求获得不少于给定价值所需的最小代价。下文记物品的代价为\(w\),价值为\(v\),所拿的数量为\(cnt\)。假设有两种物品\(S\)与\(T\),\(S\)物品的性价比......
  • P10678 『STA - R6』月 题解
    Solution看了别的大佬的题解,感觉都是数学证明然后用树和图做的,看不懂啊。。。萌新瑟瑟发抖用vector模拟树,然后贪心摸索做出来了。注意到要求最深叶子结点和最浅叶子结点的距离最短时的情况,那么此时根节点应该是树中度数最大的点,把树尽可能的拓宽,深度换宽度。那么同理的根节点......
  • 题解:P11008 『STA - R7』异或生成序列
    Solution序列\(p\)是\(1\)~\(n\)的排列,因此考虑搜索回溯。由\(\sumn\le2\times10^6\)得知\(O(n^2)\)会炸,深感遗憾但仍考虑剪枝。坚信深搜过百万的蒟蒻。。。原\(b\)序列为长度\(n-1\)的序列:{\(b_1,b_2,b_3\cdotsb_n-1\)}将其前面插入一个元素\(......
  • 题解:AT_abc374_d [ABC374D] Laser Marking
    看到\(n\le6\),就知道这道题又是一道搜索了。题面有点长,信息也给的有点多,但稍微分析就可以得到只需要搜索印刷线段的顺序即可。具体的,我们在深搜函数里面传\(4\)个参数,分别代表已选线段的数量,当前位置的横纵坐标,以及当前时间。为了方便,我们表示的是已经印刷完当前线段后的时间......
  • P5593 题解
    题目分析首先考虑什么样的颜色能被链覆盖。容易想到当某种颜色恰巧在一条链上会被覆盖。所以只需要判断一种颜色是否能构成链即可,链的贡献也很好计算。算法考虑链的性质:有且仅有两个端点。凭借这个性质,可以判断一种颜色是否在一条链上。在dfs中考虑各种情况。假设一个......
  • P10418 [蓝桥杯 2023 国 A] 相连的边 题解
    一个比较有趣的树形DP,情况比较多。【题目简述】给定一棵树,求三条相连的边,其边权之和最大。【思路】以X代表当前节点,S表示儿子,G表示孙子,P表示父节点。首先把树建出来,在以下图中,我们模拟二号点的DP过程,考虑以下几种情况:有一条边指向父节点时FG(FatherGrandson):一......