【PAT甲级】1085 Perfect Sequence (25 分)
2024-09-06 22:25:25
题意:
输入两个正整数N和P(N<=1e5,P<=1e9),接着输入N个正整数。输出一组数的最大个数使得其中最大的数不超过最小的数P倍。
trick:
测试点5会爆int,因为P太大了。。。
AAAAAccepted code:
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
long long val;
bool flag;
};
bool cmp(node a,node b){
if(a.val!=b.val)
return a.val<b.val;
return a.flag>b.flag;
}
node a[];
map<int,int>pos;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,p;
cin>>n>>p;
for(int i=;i<=n;++i)
cin>>a[i].val;
for(int i=;i<=n;++i){
a[i+n].val=a[i].val*p+;
a[i+n].flag=;
}
sort(a+,a++n+n,cmp);
int cnt=;
int ans=;
for(int i=;i<=n+n;++i){
if(a[i].flag==){
++cnt;
if(!pos[a[i].val])
pos[a[i].val]=cnt;
}
else{
int x=(a[i].val-)/p;
int tamp=cnt-pos[x]+;
ans=max(ans,tamp);
}
}
cout<<ans;
return ;
}
最新文章
- Java使用MyEclipse构建webService简单案例
- Android Support Library介绍
- CI框架如何在主目录application目录之外使用uploadify上传插件和bootstrap前端框架:
- 制作具有SSH、MySQL功能的Chroot
- Python-面向对象编程(二)
- JSP-12-使用过滤器和监听器
- Memcache 提高缓存命中率
- 生成html的几种方案
- 面向服务的体系结构(service-oriented architecture,SOA)
- 关于sql2005 与 myeclipse进行连接出现的小问题
- 遇到android.os等系统sdk包没有自动导入的情况
- Mathematica学习笔记2
- Java项目 打war包方法
- margin和padding的区别和用法
- AJAX实现登陆
- idea代码快捷
- 【资料下载区】【iCore1S相关代码、资料下载地址】更新日期2017/10/09
- hdu 1290_献给杭电五十周年校庆的礼物
- shell基础:输入输出重定向
- yum-163源配置