Greedy:Graveyard Design(POJ 2100)-白红宇

Greedy:Graveyard Design(POJ 2100)

阅读量：5287 次

发布时间：2019-06-14

本文共 1323 字，大约阅读时间需要 4 分钟。

　　题目大意，给定一个整数，要你找出他的平方和组合

　　太简单了。。。。不过一开始我储存平方和想降低时间，后来发现会超内存，直接用时间换空间了，游标卡尺法

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 10000001 5  6 using namespace std; 7 typedef long long LL_INT;  8  9 static int store[MAX_N][2];//只储存开始和结尾10 11 void Inivilize(void);12 13 int main(void)14 {15     LL_INT n, sum, tmp;16     int    s, t, num;17 18     while (~scanf("%lld", &n))19     {20         sum = num = 0; s = t = 1;21         while (1)22         {23             while ((tmp = (LL_INT)t*(LL_INT)t) <= n && sum < n)24             {25                 sum += tmp;26                 t++;27             }28             if (sum == n)29             {30                 store[num][0] = s; store[num][1] = t;31                 num++;32             }33             if (sum < n)34                 break;35             sum -= (LL_INT)s*(LL_INT)s; s++;36         }37         printf("%d\n", num);38         for (int i = 0; i < num; i++)39         {40             printf("%d ", store[i][1] - store[i][0]);41             for (int j = store[i][0]; j < store[i][1]; j++)42                 printf("%d ", j);43             printf("\n");44         }45     }46     return EXIT_SUCCESS;47 }