关于GPA Involution的思路+解法+代码

• OP
• 大体思路
• （姑且算是）解法
• AC代码
• 不当解法
• ED

题目来源：2020年浙大城市学院新生程序设计竞赛（同步赛）-K GPA Involution

OP

感谢rk学长与sl学长的倾情指导。
.

大体思路

由题意，对最终结果产生影响的只有所选A/B中最大的扣分值，所以题目的顺序对结果无关，由此我们可以按某一选项分值进行排序（接下来用A，升序），再进行处理。

首先我们先保证由A扣掉的分值尽可能小，即在排序后的某一题之前的所有题全部选A，即由A扣掉的分数为该题的A选项的扣分值。其余题（该题之后的所有题）均选择B，由B扣掉的分数即为右侧所有B扣分值的最大值。

.

（姑且算是）解法

排序之后，设题目为1,2,…,n；A选项扣分为A1,A2,…,An；B选项扣分为B1,B2,…,Bn。则如果第m(m=0,1,2,…,n,n+1)题及之前均选A，则扣分值为A_m+MIN{b_m+1,…,b_n}，对m遍历求最小值即可。

对于MIN{b_m+1,…,b_n} ，不需要在处理每个m时分别求出，
可以通过

p[n+1].b=0;
   for(i=n-1;i>=1;i--)
   {
       p[i].b=(p[i].b>p[i+1].b) ? p[i].b : p[i+1].b ;
   }

直接将B_m+1存为B_m之后（不含B_m）的最大值。
此种处理方法也在库特的鸽鸽们（以后补链）一题中，求在接收最后一次操作二后，所接受操作一的最大数值。

进一步优化：
假设排序后，B_n最大值在第x题。则在x题之前，随m的增加，由B造成的扣分值不变，均为B_n的最大值，而由A造成的扣分值增长。故只需要遍历m(m=0,x,x+1,…,n,n+1)。

AC代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct poi{
ll a,b;
}p[200005];
bool cmp(poi a,poi b)
{
    return a.a<b.a;
}
int main()
{

    ll n,i,mp,ma=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    scanf("%lld",&p[i].a);
    for(i=1;i<=n;i++)
    scanf("%lld",&p[i].b);
    sort(p+1,p+1+n,cmp);//排序
    p[n+1].b=0;
    for(i=n-1;i>=1;i--)
    {
        p[i].b=(p[i].b>p[i+1].b)?p[i].b:p[i+1].b;
    }
    mp=p[1].b;//m初始值为m=0（此时总扣分值仅为B的最大值）
    for(i=1;p[i].b!=mp;i++);//找到x
    for(;i<=n;i++)//从x之后
    {
        if(p[i].a+p[i+1].b<mp)mp=p[i].a+p[i+1].b;
    }
    printf("%lld",(mp>p[n].a)?p[n].a:mp);//m=n+1时与之前的比较
    return 0;
}

不当解法

#1
一种朴素的想法：对于每一题，比较A与B的扣分值，将较小值加入对应选项的组，最后在各组比较该组最大值，并将两组最大值求和。
对于该测试组

5
1 1 4 5 9
1 1 8 4 5

正确算法应该返回8（全选B）
而#1算法会返回9（1，2，3为A；4，5为B）

#2
一种类似DP的想法：
顺序处理每一题，选择此题选A/B对总扣分造成最小增量的情况。

5
1 1 4 5 9
1 1 8 4 5

此算法会返回9（1，2均A）或10（1，2均B）
*对于对结果影响相等的题目，在当次处理中不会造成差异，但是对以后的处理，会有后效性(来自sl）

ED

这套题真的太草了（双语）；
&我被吊锤；
&但我还是喜欢。