UVa 11100 旅行2007

https://vjudge.net/problem/UVA-11100

题意:

给定n个正整数,把它们划分成尽量少的严格递增序列,尽量均分。

思路:

因为必须严格递增,所以先统计每个数字出现的次数,次数最多的就是要划分的序列个数。

接下来每次用最多次数作为步长划分,很巧妙。

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7
 8 const int maxn = 10000 + 5;
 9 int a[maxn];
10 int vis[maxn];
11 vector<int> c[maxn];
12
13 int n;
14
15 int main()
16 {
17     //freopen("D:\\txt.txt", "r", stdin);
18     int kase = 0;
19     while (cin >> n && n)
20     {
21         if (kase)   cout << endl;
22         kase = 1;
23         memset(vis, 0, sizeof(vis));
24         for (int i = 1; i <= n; i++)
25         {
26             cin >> a[i];
27             vis[a[i]]++;
28         }
29         int cnt = 0;
30         for (int i = 1; i <= n; i++)
31         {
32             cnt = max(cnt, vis[a[i]]);
33         }
34         sort(a+1, a + n + 1);
35         cout << cnt << endl;
36         for (int i = 1; i <= cnt; i++)
37         {
38             int first = 1;
39             for (int j = i; j <= n; j += cnt)
40             {
41                 if (first)
42                 {
43                     cout << a[j];
44                     first = 0;
45                 }
46                 else   cout << " " << a[j];
47             }
48             cout << endl;
49         }
50     }
51 }
时间: 03-08

UVa 11100 旅行2007的相关文章

UVA 11100 The Trip, 2007 水题一枚

题目链接:UVA - 11100 题意描述:n个旅行箱,形状相同,尺寸不同,尺寸小的可以放在尺寸大的旅行箱里.现在要求露在最外面的旅行箱的数量最少的同时满足一个旅行箱里放的旅行箱的数量最少.求出这样满足要求的任意一种方案. 算法分析:首先我们可以确定最少的旅行箱的数量cnt:即n个旅行箱里按照尺寸大小分类(尺寸相同的在同一类),数量最多的那一类的数量.然后把cnt看成有cnt个堆,第二个要求就是要让这cnt个堆里最大旅行箱数量最小,直接用vector处理即可. 等AC之后突然想到,三个旅行箱尺寸

UVa 11100 The Trip, 2007 (题意+贪心)

题意:有n个包,其中小包可以装到大的包里,包的大小用数字进行表示,求最小的装包数量. 析:这个题的题意不太好理解,主要是有一句话难懂,意思是让每个最大包里的小包数量的最大值尽量小,所以我们就不能随便输出了, 我们先求出最少多少包,这个肯定是相同包的的最大数目了,然后输出时用等差输出,这样就能保证题目的要求. 代码如下: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #inc

UVa 11100 The Trip, 2007

今天的教训:做题要用大块的时间来做,上午做一下,做题做到一半就去忙别的事,那么后面再做的时候就无限CE,WA了.因为你很难或者需要很长时间来找回当时的思路. 题意:就像套瓷娃娃一样,有n个包,大小可能一样可能不一样,而且小的包只能被严格比它大的包包裹上.问如何打包,才能使总的包数最小,在这个前提下,还要使包裹的最多的那个包数量最少. 对这个题再抽象一次:有一个序列,要求将所有的元素划分成尽可能少的严格递增子序列,在这个前提下,最长子序列的长度尽可能少(也就是尽可能将这些元素平均分配到这些子序列中

The trip(Uva 11100)

题目大意: 给出n个数,要求将其分成最少的递增序列,保证序列最少的同时要使得序列长度的最大值最小.  n<=10000 题解: 1.我是直接看着<训练指南>里的中文题面的,lrj似乎忘记提“保证序列最少的同时要使得序列长度的最大值最小”这个条件了,WA到死..我的做法是统计每个数出现的次数,然后每次尽可能构造一个最长的序列,这样能保证序列个数最少,但是显然不满足第二个条件. 2.由于之前WA到死,就很没志气的百度了题解..然后瞄到一眼最少的序列个数就是出现次数最多的那个数的出现次数(记为

思维专题(不定期更新)

1.UVa 11100 - The Trip, 2007 题意:给出若干大小不同的包裹,小的能够装在大的包裹里面.求最小的大包裹数,并且保证在所有的大包裹中,所含有的小包裹数目最小. 思路:显然,相同大小的包只能放在不同的大包里,那么最小的大包数目就是相同大小的包的最大数目,记为k.之后,根据从小到大排序后,对于每个大包i可选取从i开始,间隔k个包的那些包裹作为该大包从里到外的各个包裹. 1 #include<iostream> 2 #include<algorithm> 3 us

大白书

UVA 11292 (简单贪心) 题意: n条恶龙,m个勇士,用勇士来杀恶龙.一个勇士只能杀一个恶龙.而且勇士只能杀直径不超过自己能力值的恶龙.每个勇士需要支付能力值一样的金币.问杀掉所有恶龙需要的最少金币. 思路: 贪心,均从小到大排序.为每一条龙找一个恰好能杀他的骑士.简单贪心. UVA 11729 (经典贪心问题) 题意: n个任务,需要交代B分钟,执行J分钟,让你合理选择交代任务的次序,求得n个任务完成的最小总时长. 思路: 经典贪心,通过比较俩俩的关系,得到整个序列的贪心排序方法.这个

大白书第一章

UVA 11292 The Dragon of Loowater(简单贪心) 题意: n条恶龙,m个勇士,用勇士来杀恶龙.一个勇士只能杀一个恶龙.而且勇士只能杀直径不超过自己能力值的恶龙.每个勇士需要支付能力值一样的金币.问杀掉所有恶龙需要的最少金币. 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 20000 + 5; 4 int n, m; 5 int night[maxn], dragon[maxn

2015 暑假

2015.07.19 1 //2015.07.19 2 3 **********做的题目*********** 4 LA 4254 5 二分最小化最大值,check函数不好写---,是一秒一秒地来处理的 6 7 UVa 11627 8 二分,写check函数的时候,用到了一点点物理的平抛,求出下落的区间的范围,再判断是否可行 9 10 UVa 11134 11 贪心,优先队列, 12 行列无关,转化为对于[1,n]中的每一个数,判断i是否在区间[l,r]里面 13 然后贪心地选择包含i点的右端点

贪心思维 专题记录 2017-7-21

A.UVa 10382 - Watering Grass 题目大意: 有一块草坪,长为l,宽为w,在它的水平中心线上有n个位置可以安装喷水装置,各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆.求出最少需要的喷水装置个数. 思路 :转化一下 将二维降成一维      d = sqrt(1.0*r*r-w*w/4.0) 接着就是区间覆盖问题了 #include <bits/stdc++.h> using namespace std; const int maxn = 10000+10;