P1193 洛谷团队训练 VS 传统团队训练

题目背景

“在中学的信息学教育领域，洛谷无疑是一个相当受欢迎的辅助网站。同时有百余所学校正在通过洛谷进行信息学竞赛（以后简称 OI）的教育。洛谷之所以如此受欢迎，是因为洛谷创新的将 OI 教育的几乎每一个环节都搬到了线上，无论是学校的竞赛教练还是学生，均可以仅仅使用这一个网站来进行练习，提升自己的能力。”

——摘自《厦门中小学教育科学研究》，2015 年 2 月号。

题目描述

XX 中学的两位信息组的教练正在为学校信息组是否应当将洛谷作为主要的训练工具而争论不休，最后决定采取一个量化的办法来决定是否迁移。

该中学的原来训练方法是，在机房的教师机里面用 cena 装载好测试数据，装载数据所需要 $T_a$ 时间，每一道题目都要装载。学生写好代码后，可以跑到教师机上收取程序并进行评测。但由于需要往返的路程，因此每跑一次就要浪费 $T_b$ 时间。所以也允许学生在自己的机子上装载好测试数据，可以根据自己的需要选择装载的题目，这需要花费和在教师机装载数据一样的时间 $T_a$，但是每次评测花费的时间就减少为 $T_c$。此外，该中学可能会用 Excel 记录各位同学的训练情况，如果某位同学的某道题的得分高于表格里的记录，那就会花费 $T_d$ 时间将这个成绩更新，否则就不必费那个事了，如果之前没有提交过这道题视为表格记录的程序为 $0$ 分。

而在洛谷中，只需要将题目和测试数据上传到洛谷，花费 $T_a$ 时间。每次评测学生只需花费 $T_c$ 时间即可。记录成绩？那是洛谷的事儿，一提交完就帮你整理好了表格根本不费时间。

看起来可以省下不少时间吧。。然而，支持传统训练方法的教练认为，洛谷并非 $100\%$ 的稳定，在有的情况会无法提供服务，因此首先要将洛谷的耗时除以它的可用度（一个小于 $100\%$ 的数字 $A\%$）并去掉小数点。又因为传统观念不易纠正，总是有不信任将题目数据交给洛谷这样的想法（kkksc03：怪我咯？），因此使用洛谷的耗时还要再加上一个罚时 $H$ 以做公平比较。

现在给出该中学的训练情况，希望你帮两位教练分析一下到底该如何选择。

输入格式

第一行，两个整数 $N,M$，代表题目数量与学生数量。

第二行，$N$ 个整数 $P_1,P_2,\dots ,P_N$，为涉及的题目编号。

第三行，$M$ 个整数 $S_1,S_2,\dots ,S_M$，为学生的学号。

第四行，七个整数 $T_a,T_b,T_c,T_d,A,H,E$，前六个数字的意义见题目描述，$E$ 如果是 $1$ 那么在 Excel 中记录成绩，如果是 $0$ 则不记录。

第五行，一个整数 $R$，代表评测数量。

接下来 $R$ 行，评测记录，每行是 ${Pr}_i,{Sr}_i,{Sc}_i$，分别为该次评测的题目号、学号以及成绩。

输出格式

三行。

第一行为传统方法的的耗时。

第二行为使用洛谷包括罚时在内的耗时。

第三行是结论，如果使用洛谷的时间小于传统方法的时间，那么输出 Use Luogu!。否则输出 Forget it...。

输入输出样例 #1

输入 #1

4 4
501 502 503 504
2 3 5 7
50 30 10 5 93 50 1
10
501 2 10
501 2 80
501 2 70
502 3 0
502 3 0
504 5 100
503 7 0
503 7 0
503 7 0
503 7 10

输出 #1

480
372
Use Luogu!

输入输出样例 #2

输入 #2

2 3
101 102
1 2 3
70 60 50 1 80 100 0
6
101 1 100
101 2 100
101 3 100
102 1 100
102 2 100
102 3 100

输出 #2

500
650
Forget it...

说明/提示

【样例解释 #1】

使用传统方法的话，装载 $4$ 道题目需要 $4\times 50=200$，$2$ 号同学和 $7$ 号同学用教师机需要时分别 $30\times 3=90$、$30\times 4=120$，但是明显自己装载 cena 只需要 $50+10\times 3=80$、$50+10\times 4=90$ 更优。而 $3,5$ 同学则使用教师机就好，耗时 $60,30$。$2$ 号同学的前两次评测单调递增，所以额外花费 $2\times 5=10$ 时间记录，$3$ 号同学太弱了都是 $0$ 分所以没必要记录了，$5$ 与 $7$ 各耗费 $5$ 时间。所以这种情况总时间耗时为 $200+80+90+60+30+10+5+5=480$。

使用洛谷的话，装载题目耗费 $200$，$10$ 次评测共耗费 $10\times 10=100$，考虑稳定性时间为 $(200+100)/93\%=322$，所以最后总耗时为 $322+50=372$，所以决定使用洛谷。

【数据范围】

其中 $50\%$ 数据中，不需要进行成绩的 Excel 记录。

其中 $50\%$ 数据中，题目编号和学号均大于等于 $0$，小于等于 $1000$。

（这两种情况，可能会重叠）

对于 $100\%$ 的数据，保证 $1\le n,m\le 1000$，$1\le T_a,T_b,T_c,T_d,H\le 10000$，$1\le R<100000$，$0\le {Sc}_i\le 100$，$1\le A\le 100$，学号和题目号在 ${10}^8$ 之内。

实际上，根据超级监控颁发的证书，洛谷 2015 年第一季度可靠性（SLA）为 $99.36\%$。同时观念也是可以改变的。

洛谷的优点很多都是不能量化的，其精华在于社区。和全国的 OIer 一起学习交流，不很好吗？

最后插一句，去年的【榨取 kkksc03】的布告依然有效，详情。

C++实现

#include
#include
#include
#include
using namespace std;
int n,m,ta,tb,tc,td,A,H,E,r,pr,sr,sc;
int tea,self,trad,luogu,p[1001],s[1001],score[1001][1001],jud[1001][1001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=m;i++) cin>>s[i];
sort(p+1,p+n+1); //排序预处理
sort(s+1,s+m+1);
cin>>ta>>tb>>tc>>td>>A>>H>>E;
cin>>r;
trad=tan; //传统导入数据初始化
for(int i=1;i<=r;i++)
{
cin>>pr>>sr>>sc;
pr=lower_bound(p+1,p+n+1,pr)-p; //二分查找离散化下标
sr=lower_bound(s+1,s+m+1,sr)-s;
if(sc>score[sr][pr]&&E) trad+=td,score[sr][pr]=sc; //excel更改
jud[sr][pr]++; //评测次数加一
}
luogu=(nta+rtc)100/A+H; //洛谷耗时
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
tea=0; self=ta; //记得重新初始化
tea+=tbjud[i][j]; //老师评测耗时
self+=tcjud[i][j]; //自己评测耗时
trad+=min(tea,self); //取更小值
}
}
cout<<trad<<endl<<luogu<<endl; //输出
if(luogu<trad) cout<<“Use Luogu!”;
else cout<<“Forget it…”;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容