2 条题解
-
0
这题感觉数据有点水。
思路很简单:我们先统计出小 R 的排名,然后根据排名排座位。
统计排名有两种方法:
- 使用一些排序算法将整个分数数组排序,因为保证分数不重复,所以直接循环遍历一遍小 R 的分数求出排名。这种方法虽然能过,但并不是最优方法。
- 直接循环统计一遍比小 R 分数高的人数,将人数 即可得到排名。相对于排序的方法,时间复杂度更优。
接下来就是排座位了。观察给出的图片,设排名为 ,得出结论:
-
当 为奇数时, 随 的增大而增大。
-
当 为偶数时, 随 的增大而减小。
这里不给出模拟的方法,给出一个直接计算答案的方法:
- 直接算出 ,显然和 有关。但是如何计算呢?可以证明, 的值为
(p-1)/n+1。 - 根据 的奇偶算出 的值。 显然和
p%n有关,但我们要考虑p%n的情况以及 的奇偶性。
- 当
p%n且 为奇数时,显然 。 - 当
p%n且 为偶数时,显然 。 - 当
p%n且 为奇数时,p%n。 - 当
p%n且 为偶数时,n-(p%n)+1。
然后输出 和 就切掉这题了。
最后给出 AC 代码:
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m,a[105],p=1; cin>>n>>m; for(int i=1;i<=n*m;i++) cin>>a[i]; for(int i=2;i<=n*m;i++) if(a[i]>a[1]) p++;//O(nm)统计排名 int c=(p-1)/n+1,r; if(c%2) r=p%n?p%n:n; else r=n-(p%n?p%n:n)+1; cout<<c<<' '<<r; return 0; }完结撒花!
- 1
信息
- ID
- 1320
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 153
- 已通过
- 54
- 上传者