Codeforces Round #392 (Div. 2)

题目链接：http://codeforces.com/contest/758/problem/C

题意：给定N*M矩阵的教室，每个位置都有一个学生，Sergei坐在[X,Y]，然后老师会问K个问题，对于行而言问的顺序是从第一行，第二行。。。第N行，第N-1行。。。第二行，第一行然后重复。对于列而言问的顺序都是从左到右，现在问你最后问完K个问题后，被提问的最多的同学的次数是多少，被提问的最少的同学的次数是多少，Sergei被提问的次数是多少。

思路：由于k的范围太大，所以不能一个一个模拟，考虑下循环节。我们以1.2.3...n.n-1...3.2位一个循环节，那么除了第一行和最后一行的人被问过一次之外，中间的都被问过两次，一次循环的人数为(n-2)*m，所以共循环了k/(n-2)*m次，剩余的(不超过(n-2)*m个)直接暴力模拟即可，最后再扫一遍即可得到答案。

注意当n=1或者n=2时要特殊处理。

import java.io.PrintWriter;

import java.util.*;

public class Main {

    public static final int MAXN=100+5;

    public static long v[][]=new long [MAXN][MAXN];

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        PrintWriter out = new PrintWriter(System.out);

        int n=cin.nextInt(),m=cin.nextInt();

        long k=cin.nextLong();

        int x=cin.nextInt(),y=cin.nextInt();

        for(int i=0;i<MAXN;i++){

            Arrays.fill(v[i], 0);

        }

        if(n==1||n==2){

            for(int i=1;i<=n;i++){

                for(int j=1;j<=m;j++){

                    v[i][j]=k/(n*m);

                }

            }

            k=k%(n*m);

            for(int i=1;i<=n&&k>0;i++){

                for(int j=1;j<=m&&k>0;j++){

                    v[i][j]++; k--;

                }

            }

        }

        else{

            for(int i=1;i<=n;i++){

                for(int j=1;j<=m;j++){

                    if(i==1||i==n){

                        v[i][j]=k/((n+n-2)*m);

                    }

                    else{

                        v[i][j]=k/((n+n-2)*m)*2;

                    }

                }

            }

            k=k%((n+n-2)*m);

            for(int i=1;i<=n&&k>0;i++){

                for(int j=1;j<=m&&k>0;j++){

                    v[i][j]++; k--;

                }

            }

            for(int i=n-1;i>=1&&k>0;i--){

                for(int j=1;j<=m&&k>0;j++){

                    v[i][j]++; k--;

                }

            }

        }

        long maxv=-1,minv=Long.MAX_VALUE;

        for(int i=1;i<=n;i++){

            for(int j=1;j<=m;j++){

                maxv=Math.max(maxv,v[i][j]);

                minv=Math.min(minv, v[i][j]);

            }

        }

        out.println(maxv+" "+minv+" "+v[x][y]);

        cin.close();

        out.flush();

    }

}

巴特西

Codeforces Round #392 (Div. 2) - C

最新文章

热门文章