UOJ #206. 【APIO2016】Gap

有

你的程序不能直接读入这个整数序列,但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节,请根据你所使用的语言,参考下面的实现细节部分。

你需要实现一个函数,该函数返回

实现细节

本题只支持 C/C++/Pascal。

C/C++

你需要包含头文件 gap.h。

你需要实现一个函数 findGap(T, N)，该函数接受下面的参数，并返回一个 long long 类型的整数：

你的函数 findGap 可以调用系统提供的查询函数 MinMax(s, t, &mn, &mx)，该函数的前两个参数

Pascal

你需要使用单元 graderhelperlib。

你需要实现一个函数 findGap(T, N)，该函数接受下面的参数，并返回一个 Int64 类型的整数：

你的函数 findGap 可以调用系统提供的查询函数 MinMax(s, t, mn, mx)，该函数的前两个参数

样例一

C/C++

考虑

则答案应该是

调用 MinMax(1, 2, &mn, &mx)，则 mn 和 mx 皆返回
调用 MinMax(3, 7, &mn, &mx)，则 mn 返回
调用 MinMax(8, 9, &mn, &mx)，则 mn 和 mx 皆返回

Pascal

考虑

则答案应该是

调用 MinMax(1, 2, mn, mx)，则 mn 和 mx 皆返回
调用 MinMax(3, 7, mn, mx)，则 mn 返回
调用 MinMax(8, 9, mn, mx)，则 mn 和 mx 皆返回

样例评测方式

样例测评系统从标准输入中读入两行。第一行包含两个整数，子任务编号

下面的输入描述了上面的样例：

2 4
2 3 6 8

限制与约定

对于所有的测试点，有

每一个测试点开始测试之前，

子任务 1（30 分）：每一次调用 MinMax 都将使

子任务 2（70 分）：定义

交互式类型的题目怎么本地测试

时间限制：

空间限制：

下载

样例及测评库下载

题解

人生中第一道交互题

前30分很好拿然而我交了好几次才拿到......因为根本没看清题

subtask 2 我觉得很有趣

首先把差的平均数算出来然后答案肯定大于这个平均数

这样就可以少管很多没用的数了

谁搞的hack数据......卡掉了我3分...

#include "gap.h"
#include<cstdio>
#include<algorithm>
#define M 200005
using namespace std;
long long a[M];
long long findGap(int T, int N)
{
    long long ans=0,head,tail;
    MinMax(0,(long long)1e18,&head,&tail);
    if(T==1)
    {
        a[1]=head;a[N]=tail;
        for(int i=2,j=N-1;i<=j;i++,j--)
        {
            MinMax(head+1,tail-1,&head,&tail);
            a[i]=head;a[j]=tail;
        }
        for(int i=1;i<N;i++)ans=max(ans,a[i+1]-a[i]);
        return ans;
    }
    else
    if(N==2)return tail-head;
    else
    {
        int t=0;
        long long ave=(tail-head-1)/N+1,begin=head,end=tail;
        a[++t]=begin;
        for(long long i=begin;i<end;i+=ave)
        {
         //   if(i+1<=min(i+ave,end-1))
            MinMax(i+1,min(i+ave,end-1),&head,&tail);
         //   else continue;
            if(head==-1 && tail==-1)continue;
            a[++t]=head;a[++t]=tail;
        }
        a[++t]=end;
        for(int i=1;i<t;i++)ans=max(ans,a[i+1]-a[i]);
        return ans;
    }
    return 0;
}

交互感觉还是很有趣的一种题型

有趣不代表会做......

明天APIO rp++ (这么晚了还不睡明天是要爆零了......)

实现细节

C/C++

Pascal

样例一

C/C++

Pascal

样例评测方式

限制与约定

下载

相关推荐