余冉旭
(余冉旭)
1
题目描述
你有n个立方体，要用它们建造塔。每当两个立方体叠在一起时，上面的立方体必须比下面的立方体小。你必须按照给定的顺序处理立方体。你可以将立方体放在现有的塔上，也可以开始新的塔。请问最少需要多少个塔？
输入格式
从文件towers.in 中读入数据。
第一行包含一个整数n：立方体的数量。接下来一行包含n个整数k1，k2，…，kn：立方体的大小。
输出格式
输出到文件towers.out 中。
输出一个整数：最少需要的塔的数量。
样例
Input 1
5
3 8 2 1 5
Output 1
2
数据范围
1 ≤ n ≤ 2 * 10^5，1 ≤ ki ≤ 10^9
样例解释
对于样例1，可以分别将立方体2和立方体1放在不同的塔上，所以最少需要2个塔。
代码如下:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
using namespace std;
long long n,k,j[200005],a;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
freopen("towers.in","r",stdin);
freopen("towers.out","w",stdout);
cin>>n;for(int i=1;i<=n;i++)
{
cin>>k;
for(int x=1;x<=n;x++)
{
if(j[x]>k)
{
j[x]=k;
break;
}
if(j[x]==0)
{
j[x]=k;
a++;
break;
}
}
}cout<<a;return 0;
}
4 个赞
Syxqwq
(Loser_Syx)
5
我个人认为哈，对于每个 a_i ，如果它能放置，则一定贪心地选择最小的那个塔放
4 个赞
林嘉乐
(A_GreenBlueBerry)
6
虽然忘了文件读写怎么弄但是样例过了awa
你试试，我这个内循环边界是塔的数量，应该不会超时 吧
#include<bits/stdc++.h>
using namespace std;
//tower记录每个塔的大小，cnt记录塔的个数
long long n,k[200005],tower[200005],cnt=1;
int main()
{
//输入和运算放一个循环了
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&k[i]);
if(i==1) tower[1]=k[1];//第一个立方体作新的塔
//在tower数组里寻找合适的塔↓
int flag=0;
for(int j=1; j<=cnt; j++)
{
//找到则跳出循环,cnt不变,flag变为1
if(k[i]<=tower[cnt])
{
flag=1;
break;
}
}
if(flag==0) //当循环结束flag仍为0，则未找到
{
cnt++;//塔的数量增加
tower[cnt]=k[i];//创建新塔
//重新升序排序 以确保从小到大寻找(你说的贪心思路
sort(tower+1,tower+1+cnt) ;
}
}
//然后就输出啦qwq
printf("%d",cnt);
return 0;
}
这个是没注释的↓
#include<bits/stdc++.h>
using namespace std;
long long n,k[200005],tower[200005],cnt=1;
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&k[i]);
if(i==1) tower[1]=k[1];
int flag=0;
for(int j=1; j<=cnt; j++)
{
if(k[i]<=tower[cnt])
{
flag=1;
break;
}
}
if(flag==0)
{
cnt++;
tower[cnt]=k[i];
sort(tower+1,tower+1+cnt) ;
}
}
printf("%d",cnt);
return 0;
}
3 个赞
袁少
(烈焰·行仓)
7
看了是先降序，判断如果相同，开一个新的塔，否则在原来的塔上叠
2 个赞
林嘉乐
(A_GreenBlueBerry)
12
有人解决了私信我一下，现在这已经是我们两个的问题了·-·
3 个赞
