2013编程之美の长方形

题目是这样子的:

描述

在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。

输入

输入文件包含多组测试数据。
第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N,M,K。
1 ≤ T ≤ 100
0 ≤ K ≤ N * M
小数据:0 < N, M ≤ 30
大数据:0 < N, M ≤ 30000

输出

对于每组测试数据,输出一行”Case #X: Y”,其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

样例输入

3
3 3 8
4 5 13
7 14 86

样例输出

Case #1: 5
Case #2: 18
Case #3: 1398

直观上有这么一种思路:先对给定的点数K开根号,因为我们有限制K

  1. //import java.io.FileNotFoundException;   
  2. //import java.io.FileReader;   
  3. import java.util.Scanner;   
  4.     
  5. public class Main {   
  6.     //热身赛2-长方形   
  7.     public static void main(String[] args) {   
  8.         int classNum = -1;   
  9.         String secondLineStr;   
  10.         int N = -1;   
  11.         int M = -1;   
  12.         int K = -1;   
  13.         int min_Edge = 0;   
  14.         int max_Edge = 0;   
  15.         int squre_root = 0;   
  16.         int first_Part = 0;   
  17.         int surplus = 0;   
  18.         int second_Part = 0;   
  19.         StringBuffer result = new StringBuffer();   
  20. //      FileReader fin = null;   
  21. //      try {   
  22. //          fin = new FileReader(“1.txt”);   
  23. //      } catch (FileNotFoundException e) {   
  24. //          e.printStackTrace();   
  25. //      }   
  26.         @SuppressWarnings(“resource”)   
  27. //      Scanner in = new Scanner(fin);   
  28.         Scanner in = new Scanner(System.in);   
  29.         classNum = Integer.valueOf(in.nextLine());   
  30.         for (int i = 0; i < classNum; i++) {   
  31.             result.append(“Case #”);   
  32.             result.append(i+1);   
  33.             result.append(“: ”);   
  34.             secondLineStr = in.nextLine();   
  35.             N = Integer.valueOf(secondLineStr.split(“\\s+”)[0]);   
  36.             M = Integer.valueOf(secondLineStr.split(“\\s+”)[1]);   
  37.             K = Integer.valueOf(secondLineStr.split(“\\s+”)[2]);   
  38.             min_Edge = N < M ? N : M;   
  39.             max_Edge = N > M ? N : M;   
  40.             squre_root = (int) Math.sqrt(K);   
  41.             if ((squre_root <= 1) ||(min_Edge <= 1)) {   
  42.                 first_Part = 0;   
  43.                 second_Part = 0;   
  44.             }else if(K >= N*M) {   
  45.                 first_Part = N*M*(N-1)*(M-1)/4;   
  46.                 second_Part = 0;   
  47.             }else {   
  48.                 if (squre_root < min_Edge) {   
  49.                     first_Part = squre_root*squre_root*(squre_root-1)*(squre_root-1)/4;   
  50.                     surplus = K - squre_root*squre_root;   
  51.                     if ((surplus > 1) && (surplus <= squre_root)) {   
  52.                         second_Part = squre_root * surplus * (surplus-1) /2;   
  53.                     }else if (surplus == (squre_root+1)) {   
  54.                         second_Part = squre_root * squre_root * (squre_root-1) /2;   
  55.                     }else if (surplus > (squre_root + 1)) {   
  56.                         if (max_Edge > squre_root+1) {   
  57.                             second_Part = squre_root * squre_root * (squre_root-1) /2 + (squre_root+1)*(surplus - squre_root)*(surplus - squre_root -1)/2;     
  58.                         }else {   
  59.                             second_Part = squre_root * squre_root * (squre_root-1) /2 + squre_root*(surplus - squre_root)*(surplus - squre_root -1)/2;   
  60.                         }   
  61.                     }else {   
  62.                         second_Part = 0;   
  63.                     }   
  64.                 }else {   
  65.                     int row_count = K / min_Edge;   
  66.                     first_Part = min_Edge*row_count*(min_Edge-1)*(row_count-1)/4;   
  67.                     surplus = K - min_Edge*row_count;   
  68.                     second_Part = row_count * surplus*(surplus -1)/2;   
  69.                 }   
  70.             }   
  71.             result.append(first_Part+second_Part);   
  72.             System.out.println(result.toString());   
  73.             result.delete(0, result.length());   
  74.         }   
  75.     }   
  76. }  

这时,提交代码是屡屡出错,大多数能想到的可能性已经进行测试:

样例输入

12
5 5 10
5 5 15
3 3 8
0 0 4
0 14 6
1 10 9
4 5 13
7 14 86
3 6 16
5 5 1
5 5 9
5 5 11
5 5 14
5 4 18
5 4 22
5 4 20

样例输出

Case #1: 9
Case #2: 30
Case #3: 5
Case #4: 0
Case #5: 0
Case #6: 0
Case #7: 18
Case #8: 1398
Case #9: 30
Case #10: 0
Case #11: 9
Case #12: 12

但就是无法提交通过,无奈之下继续查看其他人的方法,在这篇博客http://www.cnblogs.com/wuminye/archive/2013/04/07/3006425.html中发现异同,盲目着追求正方形的思路是错误的,可以想到的例子就是 5 5 10,如果采用第一种方法的话就是先构造一个3*3的正方形,然后多余的1个点被舍弃,那么结果就是9。然而在第二种方法中进行了遍历操作,首先尽可能着构造一个正方形,然后开始把一个边进行压缩到最小值2,遍历出所有可能性,可以找到一个最大值10:

  1. #include <stdio.h>   
  2. #include <string.h>   
  3. #include <math.h>   
  4. int n,m,k;   
  5. void swap(int &a,int &b)   
  6. {   
  7.     int t=a;   
  8.     a=b;   
  9.     b=t;   
  10. }   
  11. long long getc(long long j)   
  12. {   
  13.     return j*(j-1)/2;   
  14. }   
  15. int main()   
  16. {   
  17.    int T;   
  18.    scanf(“%d”,&T);   
  19.    int cas=0;   
  20.    while (T–)   
  21.    {   
  22.        scanf(“%d%d%d”,&n,&m,&k);   
  23.        if (n<m) swap(n,m);   
  24.        int t=sqrt(k);   
  25.        int b=t>m?m:t;   
  26.        int a=k/b>n?n:k/b;   
  27.        long long max=0;   
  28.        for (;b>=2 && a<=n;–b,a=k/b)   
  29.        {   
  30.            long long sum=getc(a)*getc(b);   
  31.            int p=k-a*b;   
  32.            if (a<n)   
  33.            {   
  34.               sum=sum+getc(p)*a;   
  35.            }   
  36.             else  
  37.             {   
  38.                 sum=sum+getc(p)*b;   
  39.             }   
  40.             max=max>sum?max:sum;   
  41.        }   
  42.        printf(“Case #%d: %lld\n”,++cas,max);   
  43.    }   
  44.   
  45.  return 0;   
  46. }  

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>