hdu 刷题记录
2024-09-27 11:19:22
1007 最近点对问题,采用分治法策略搞定
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
struct node
{
double x;
double y;
}p[];
int a[];
double cmpx(node a,node b)
{
return a.x<b.x;
}
double cmpy(int a,int b)
{
return p[a].y<p[b].y;
}
double min(double a,double b)
{
return a<b?a:b;
}
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double find(int l,int r)
{
if(r==l+)
return dis(p[l],p[r]);
if(l+==r)
return min(dis(p[l],p[r]),min(dis(p[l],p[l+]),dis(p[l+],p[r])));
int mid=(l+r)>>;
double ans=min(find(l,mid),find(mid+,r));
int i,j,cnt=;
for(i=l;i<=r;i++)
{
if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)
a[cnt++]=i;
}
sort(a,a+cnt,cmpy);
for(i=;i<cnt;i++)
{
for(j=i+;j<cnt;j++)
{
if(p[a[j]].y-p[a[i]].y>=ans) break;
ans=min(ans,dis(p[a[i]],p[a[j]]));
}
}
return ans;
}
int main()
{
int i; while(scanf("%d",&n)!=EOF)
{
if(!n) break;
for(i=;i<n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
sort(p,p+n,cmpx);
printf("%.2lf%\n",find(,n-)/);
}
return ;
}
1008 沙茶题,水题预警
#include<stdio.h>
int main()
{
int n;
int start,a;
int t;
int i;
while(scanf("%d",&n),n)
{
t=;start=;
for(int i=;i<=n;i++)
{
scanf("%d",&a);
if(a>start)t+=*(a-start);
else t+=*(start-a);
t+=;
start=a;
}
printf("%d\n",t);
}
return ;
}
1009 贪心排序乱搞一波
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include<vector>
#include<map>
#include<deque>
#include<list>
using namespace std;
typedef struct node{
int j;
int f;
double d;
}MC;
MC a[];
bool cmp(MC a,MC b)
{
return a.d>b.d;
}
int main()
{
int n,m,i;
double t;
while(cin>>n>>m)
{
if(n==-&&m==-)
break;
for(int i=;i<m;i++)
{
cin>>a[i].j>>a[i].f;
a[i].d=1.0*a[i].j/a[i].f;
}
sort(a,a+m,cmp);
t=;
for(int i=;i<m;i++)
{
if(n>a[i].f)
{
t+=a[i].j;
n-=a[i].f;
}
else
{
t+=n*a[i].d;break;
}
}
printf("%.3lf\n",t);
}
return ;
}
2710 机智的离线打表
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include<vector>
#include<map>
#include<deque>
#include<list>
using namespace std;
int a[]={,};
int main()
{
for(int i=;i<=;i++)
{
if(a[i]==)
{
for(int j=i;j<=;j+=i)
a[j]=i;
}
}
int n;
while(scanf("%d",&n)!=EOF)
{
int ans;
int maxn=;
while(n--)
{
int m;
scanf("%d",&m);
if(a[m]>maxn)
{
ans=m;
maxn=a[m];
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- .NET平台开源项目速览(16)C#写PDF文件类库PDF File Writer介绍
- 从游戏脚本语言说起,剖析Mono所搭建的脚本基础
- SharedPreferences 详解
- maven Error resolving version for plugin &#39;org.apache.maven.plugins:maven-eclipse-plugin&#39; from the repositories 解决
- POJ 2559
- IOS第11天(1:UIPickerView点餐)
- 浅析 Linux 初始化 init 系统,第 1 部分: sysvinit 第 2 部分: UpStart 第 3 部分: Systemd
- kuangbin_UnionFind J (POJ 2492)
- sqlserver安装相关问题
- ubuntu安装python3
- 百度云管家-V4.6.1-单文件版绿色版
- 小Q书桌的下载、安装和使用
- Unity 单元测试(PLUnitTest工具)
- 2014百度之星预赛(第二场)——Best Financing
- SQL Server中的高可用性1
- Zend:PHP框架结束的开始?
- ARMV7-M数据手册---Part B :System Level Architecture---B3 System Address Map
- mysql系列十三、mysql中replace into和duplicate key的使用区
- Linux基础命令---文本编辑ex
- 使用Redis做分布式