KS3. 搭积木
描述
输入描述
第一行为积木的总个数 N输出描述
输出总共可以搭的层数示例1
输入:
5 2 2 2 4 3 3 2 5 4 5
输出:
4
C++ 解法, 执行用时: 133ms, 内存消耗: 16504KB, 提交时间: 2020-11-17
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<regex>
#include<queue>
#include<algorithm>
#include<deque>
#include<cmath>
#include<set>
#include<cstring>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf = 2147483647;
//----------------
// #define int long long
//----------------
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
#define me(a,b) memset(a,b,sizeof(a))
#define sdf(x) x=read()
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FFor(i, a, b) for (int i = (a); i >= (b); i--)
#define bg1(x) cout<<(#x)<<":"<<(x)<<" "<<endl
#define bg2(x,y) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<endl
#define bg3(x,y,z) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<endl
#define bg4(x,y,z,w) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<endl
#define bg5(x,y,z,w,k) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<(#k)<<":"<<(k)<<" "<<endl
#define lll cout<<"\n------\n"
int die = 0;
#define Die die++;if(die>100000){cout<<"dead!!!";exit(0);}
const double eps = 1e-9;
// srand((unsigned)time(NULL));
const int mod = 1e9 + 7;
const int N1 = 1e6 + 5;
int n;
struct node{
int l,w;
}a[N1];
int b[N1];
void sol1(){
// cout<<inf<<endl;
sort(a+1,a+1+n,[](node x,node y){return x.l==y.l?x.w<y.w:x.l<y.l;});
For(i,1,n)b[i]=inf;
int ans=1;
For(i,1,n){
int x=upper_bound(b+1,b+1+ans,a[i].w)-b;
// bg1(x);
ans=max(ans,x);
b[x]=a[i].w;
}
cout<<ans;
}
void rd(){
sdf(n);
For(i,1,n)sdf(a[i].l),sdf(a[i].w);
sol1();
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
rd();
}
C++ 解法, 执行用时: 134ms, 内存消耗: 16456KB, 提交时间: 2020-10-29
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<regex>
#include<queue>
#include<algorithm>
#include<deque>
#include<cmath>
#include<set>
#include<cstring>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf = 2147483647;
//----------------
// #define int long long
//----------------
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
#define me(a,b) memset(a,b,sizeof(a))
#define sdf(x) x=read()
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FFor(i, a, b) for (int i = (a); i >= (b); i--)
#define bg1(x) cout<<(#x)<<":"<<(x)<<" "<<endl
#define bg2(x,y) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<endl
#define bg3(x,y,z) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<endl
#define bg4(x,y,z,w) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<endl
#define bg5(x,y,z,w,k) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<(#k)<<":"<<(k)<<" "<<endl
#define lll cout<<"\n------\n"
int die = 0;
#define Die die++;if(die>100000){cout<<"dead!!!";exit(0);}
const double eps = 1e-9;
// srand((unsigned)time(NULL));
const int mod = 1e9 + 7;
const int N1 = 1e6 + 5;
int n;
struct node{
int l,w;
}a[N1];
int b[N1];
void sol1(){
// cout<<inf<<endl;
sort(a+1,a+1+n,[](node x,node y){return x.l==y.l?x.w<y.w:x.l<y.l;});
For(i,1,n)b[i]=inf;
int ans=1;
For(i,1,n){
int x=upper_bound(b+1,b+1+ans,a[i].w)-b;
// bg1(x);
ans=max(ans,x);
b[x]=a[i].w;
}
cout<<ans;
}
void rd(){
sdf(n);
For(i,1,n)sdf(a[i].l),sdf(a[i].w);
sol1();
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
rd();
}
C++ 解法, 执行用时: 134ms, 内存消耗: 16540KB, 提交时间: 2020-10-29
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<regex>
#include<queue>
#include<algorithm>
#include<deque>
#include<cmath>
#include<set>
#include<cstring>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf = 2147483647;
//----------------
// #define int long long
//----------------
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
#define me(a,b) memset(a,b,sizeof(a))
#define sdf(x) x=read()
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FFor(i, a, b) for (int i = (a); i >= (b); i--)
#define bg1(x) cout<<(#x)<<":"<<(x)<<" "<<endl
#define bg2(x,y) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<endl
#define bg3(x,y,z) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<endl
#define bg4(x,y,z,w) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<endl
#define bg5(x,y,z,w,k) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<(#k)<<":"<<(k)<<" "<<endl
#define lll cout<<"\n------\n"
int die = 0;
#define Die die++;if(die>100000){cout<<"dead!!!";exit(0);}
const double eps = 1e-9;
// srand((unsigned)time(NULL));
const int mod = 1e9 + 7;
const int N1 = 1e6 + 5;
int n;
struct node{
int l,w;
}a[N1];
int b[N1];
void sol1(){
// cout<<inf<<endl;
sort(a+1,a+1+n,[](node x,node y){return x.l==y.l?x.w<y.w:x.l<y.l;});
For(i,1,n)b[i]=inf;
int ans=1;
For(i,1,n){
int x=upper_bound(b+1,b+1+ans,a[i].w)-b;
// bg1(x);
ans=max(ans,x);
b[x]=a[i].w;
}
cout<<ans;
}
void rd(){
sdf(n);
For(i,1,n)sdf(a[i].l),sdf(a[i].w);
sol1();
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
rd();
}
C++ 解法, 执行用时: 136ms, 内存消耗: 16508KB, 提交时间: 2020-12-22
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<regex>
#include<queue>
#include<algorithm>
#include<deque>
#include<cmath>
#include<set>
#include<cstring>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf = 2147483647;
//----------------
// #define int long long
//----------------
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
#define me(a,b) memset(a,b,sizeof(a))
#define sdf(x) x=read()
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FFor(i, a, b) for (int i = (a); i >= (b); i--)
#define bg1(x) cout<<(#x)<<":"<<(x)<<" "<<endl
#define bg2(x,y) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<endl
#define bg3(x,y,z) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<endl
#define bg4(x,y,z,w) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<endl
#define bg5(x,y,z,w,k) cout<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#w)<<":"<<(w)<<" "<<(#k)<<":"<<(k)<<" "<<endl
#define lll cout<<"\n------\n"
int die = 0;
#define Die die++;if(die>100000){cout<<"dead!!!";exit(0);}
const double eps = 1e-9;
// srand((unsigned)time(NULL));
const int mod = 1e9 + 7;
const int N1 = 1e6 + 5;
int n;
struct node{
int l,w;
}a[N1];
int b[N1];
void sol1(){
// cout<<inf<<endl;
sort(a+1,a+1+n,[](node x,node y){return x.l==y.l?x.w<y.w:x.l<y.l;});
For(i,1,n)b[i]=inf;
int ans=1;
For(i,1,n){
int x=upper_bound(b+1,b+1+ans,a[i].w)-b;
// bg1(x);
ans=max(ans,x);
b[x]=a[i].w;
}
cout<<ans;
}
void rd(){
sdf(n);
For(i,1,n)sdf(a[i].l),sdf(a[i].w);
sol1();
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
rd();
}
C++ 解法, 执行用时: 137ms, 内存消耗: 4268KB, 提交时间: 2021-02-23
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000000;
struct node{
int x,y;
bool operator<(const node& t) const{
return (x < t.x)||(x == t.x&&y<t.y);
}
};
int N;
int main(){
ios::sync_with_stdio(false);
cin >> N;
struct node arr[N];
for(int i=0;i<N;i++)
{
cin >> arr[i].x;
cin >> arr[i].y;
}
sort(arr, arr+N);
//对长求最长上升子序列
vector<int> dp; //保存最长上升子序列
for(int i=0;i<N;i++)
{
if(dp.empty()||arr[i].y>=dp.back())
{
dp.push_back(arr[i].y);
}
else
{
//第一个大于arr[i][1]的数
*(upper_bound(dp.begin(), dp.end(), arr[i].y)) = arr[i].y;
}
}
cout << dp.size() << endl;
}