P8278 「MCOI-08」【A】Fill In

· · 题解

题目传送门

在此食用味道更佳

前置芝士：

c++ 中的整除：

设三个正整数分别为 a ， b ， c ，且：

a=\frac{c}{b}

那么在 c++ 的运算中，会出现两种情况：

那么在后面的程序中就会讲到怎么使用这两个性质

思路：

由于给出的是前缀和数组中的一部分，那么当前到上一个给出的前缀和的位置之间的数就可以求出来了。

首先先放查找从当前位开始给出的最近前缀和的位置的代码：

inline int findid(int s){
    for(int i=s;i<=n;i++){
        if(p[i]!=-1)return i;// 找到给出的前缀和则返回当前位置
    }
    return -1;// 否则返回 -1
}

设 q 为当前前缀和的位置， lq 为上一个前缀和的位置， gc 是两个前缀和之差

那么就可以分 5 种情况：

  1. ```cpp if(lq==n)break; ``` 跳出循环
  1. ```cpp if(lq<n&&q==-1){ for(int i=lq+1;i<=n;i++)cout<<1<<" "; break; } ``` $lq+1$ 到 $n$ 之间的数全部输出 1
  1. ```cpp if(gc==1){ for(int i=lq+1;i<q;i++)cout<<0<<" "; cout<<1<<" "; } ``` $lq+1$ 到 $q-1$ 之间的数输出 0 ， $q$ 的位置输出 1
  1. ```cpp if(gc==0){ for(int i=lq+1;i<=q;i++)cout<<0<<" "; } ``` $lq+1$ 到 $q$ 之间的数输出 0
  1. 正常情况（每个值平均输出）： 
    int qq=gc/(q-lq);// 取平均值
if(qq*(q-lq)!=gc){// 当不能整除时
    for(int i=lq+1;i<q;i++)cout<<qq<<" ";//先输出向下取整的平均值
    cout<<gc-(q-lq-1)*qq<<" ";//最后输出余下的值
}else{//当能整除时
    for(int i=lq+1;i<=q;i++)cout<<qq<<" ";//直接输出平均值
}

思考题：为什么正常情况下必须每个值平均输出，而不能前面的值输出 0 ，最后的直接输出 gc 的值？（答案在文章的最后面）

AC 代码就不放注释了，自己理解更好

CODE ：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-')f=-1;
    for(;c<='9'&&c>='0';c=getchar())
        x=(x<<3)+(x<<1)+(c^48);
    return (f==1?x:-x);
}
int t,n,p[100005],gc;
inline int findid(int s){
    for(int i=s;i<=n;i++){
        if(p[i]!=-1)return i;
    }
    return -1;
}
signed main(){
    t=read();
    p[0]=0;
    while(t--){
        n=read();
        for(int i=1;i<=n;i++)p[i]=read();
        int q=findid(1),lq=0;
        if(q==-1){
            for(int i=1;i<=n;i++)cout<<i<<" ";
            cout<<endl;
        }else{
            while(1){
                if(lq==n)break;
                if(lq<n&&q==-1){
                    for(int i=lq+1;i<=n;i++)cout<<1<<" ";
                    break;
                }
                gc=p[q]-p[lq]; 
                if(gc==1){
                    for(int i=lq+1;i<q;i++)cout<<0<<" ";
                    cout<<1<<" ";
                }else if(gc==0){
                    for(int i=lq+1;i<=q;i++)cout<<0<<" ";
                }else{
                    int qq=gc/(q-lq);
                    if(qq*(q-lq)!=gc){
                        for(int i=lq+1;i<q;i++)cout<<qq<<" ";
                        cout<<gc-(q-lq-1)*qq<<" ";
                    }else{
                        for(int i=lq+1;i<=q;i++)cout<<qq<<" ";
                    }
                }
                lq=q;
                q=findid(q+1);
            }
            cout<<endl;
        }
    }
    return 0;
}

思考题答案：

由于题目中的数据范围有这么一句话：

满足 1 \le a_i \le 1000

所以如果不平均地输出的话，可能会超过这个限制（只有 50 分）