首页 > 代码库 > UVa 11100 The Trip, 2007

UVa 11100 The Trip, 2007

2024-07-22 13:11:55   221人阅读

今天的教训：做题要用大块的时间来做，上午做一下，做题做到一半就去忙别的事，那么后面再做的时候就无限CE，WA了。因为你很难或者需要很长时间来找回当时的思路。

 

题意：就像套瓷娃娃一样，有n个包，大小可能一样可能不一样，而且小的包只能被严格比它大的包包裹上。问如何打包，才能使总的包数最小，在这个前提下，还要使包裹的最多的那个包数量最少。

对这个题再抽象一次：有一个序列，要求将所有的元素划分成尽可能少的严格递增子序列，在这个前提下，最长子序列的长度尽可能少(也就是尽可能将这些元素平均分配到这些子序列中)。

分析：

确定子序列的个数:子序列的个数就等于原序列中重复元素最多的次数

每个子序列的长度:假设原序列长度是n，子序列的个数是m。那么每个子序列的长度就是n/m 或 n/m + 1 (除法是向下取整)

如何尽量平均分配:将原序列从小到大排序后，从第一个元素开始，依次取后面的第m个元素，直到取到尽头，这是第一个子序列。第二个子序列就是从第二个元素开始取，以此类推。

保证元素的平均分配这是比较显然的了吧。

因为重复最多的才重复m次，所以元素a后面的第m个元素必定大于它，这保证了子序列的严格递增。

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 1000000 + 10; 9 int a[maxn], b[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("11100in.txt", "r", stdin);15     #endif16 17     int n;18     bool flag = false;19     while(scanf("%d", &n) == 1 && n)20     {21         int times = 0, i, j;22         if(flag)    printf("\n");23         flag = true;24         25         memset(b, 0, sizeof(b));26         for(i = 0; i < n; ++i)27         {28             scanf("%d", &a[i]);29             ++b[a[i]];30             times = max(times, b[a[i]]);31         }32 33         printf("%d\n", times);34         sort(a, a + n);35         for(i = 0; i < times; ++i)36         {37             for(j = i; j < n - times; j += times)38                 printf("%d ", a[j]);39             printf("%d\n", a[j]);40         }41     }42     return 0;43 }
代码君

 

UVa 11100 The Trip, 2007


联系
我们