poj 1328贪心算法，一直WA

`````` #include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;

struct dot
{
int x;
int y;
}abc[10000];

float left(dot a,int r)
{
return a.x - sqrt(r*r*1.0 - a.y*a.y*1.0);
}

float right(dot a, int r)
{
return a.x + sqrt(r*r*1.0 - a.y*a.y*1.0);
}

int comp(const void* a, const void* b)
{
int aa = (*(dot*)a).x;
int bb = (*(dot*)b).x;
return aa - bb;
}

int main()
{
int num, r;
cin >> num >> r;
bool flag = false;
int count = 0;
int ans[1000];
memset(ans, 0, sizeof(ans));
while (num != 0 && r != 0)
{
count++;
int cir = 0;
for (int i = 0; i < num; i++)
{
dot temp;
cin >> temp.x >> temp.y;
if (temp.y > r||temp.y<0)
flag = true;
abc[i] = temp;
}
if (flag)
{
ans[count] = -1;
cout << "Case " << count << ": " << -1 << endl;
}
else
{
qsort(abc, num, sizeof(abc[0]), comp);
dot temp = abc[0];
cir++;
float now = right(temp, r);
for (int i = 1; i < num; i++)
{
temp = abc[i];
if (now >= left(temp, r))
continue;
else
{
now = right(temp, r);
cir++;
}
}
ans[count] = cir;
cout << "Case " << count << ": " << cir << endl;
}

cin >> num >> r;
}

return 0;

}
``````

1个回答

poj1328求大神 题意如下
Input The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. The input is terminated by a line containing pair of zeros Output For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case. Sample Input 3 2 1 2 -3 1 2 1 1 2 0 2 0 0 Sample Output Case 1: 2 Case 2: 1 题意：假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。 题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。 ``` #include <algorithm> #include <vector> #include <limits> #include <string> using namespace std; double d; int n; int t=0; bool flag = false; vector <int> ans; struct data { public: double start; double ends; }; bool compare(data a,data b) { return a.ends<b.ends; } int main() { while(cin>>n>>d&&(n!=0&&d!=0)) { vector <data> ils (n); int x,y,i; i=0; while(i!=n&&cin>>x>>y) { if(y>d) { flag = true; } data item; item.start = x - sqrt(d*d-y*y); item.ends = x + sqrt(d*d-y*y); ils[i] = item; ++i; } sort(ils.begin(),ils.end(),compare); i=0; int num = 0; double range; while(i<n) { range = ils[i].ends; while(++i<n) { if(ils[i].start>range) break; } ++num; } if(flag) { ans.push_back(-1); } else { ans.push_back(num); } n=d=i=num=0; ils.clear(); flag = false; } for(t=0;t!=ans.size();t++) { cout<<"case "<<t+1<<": "<<ans[t]<<endl; } return 0; } ```
poj 1328 Running time 错误 求助
#include<iostream> using namespace std; #include<math.h> void sort_com(int dot[][2],int num)//对小岛根据x坐标排序 { int judge=1; while(judge) { judge=0; for(int i=0;i<num-1;i++) { if(dot[i][0]>dot[i+1][0]) { int temp1=dot[i][0]; int temp2=dot[i][1]; dot[i][0]=dot[i+1][0]; dot[i][1]=dot[i+1][1]; dot[i+1][0]=temp1; dot[i+1][1]=temp2; judge=1; } } } } float range(int y,int d) //求一个岛在海岸线上所允许的圆心值范围，-1表示不存在 { if(d*d-y*y<0) return -1; return sqrt((float)(d*d-y*y)); } int select_dot(int dot[][2],int d,int num)//寻找区间最少数 { int b[100][2]; for(int i=0;i<num;i++) { float delt=range(dot[i][1],d); if(delt<0) return -1; b[i][0]=dot[i][0]-delt; b[i][1]=dot[i][0]+delt; } int center=b[0][1]; int result=1; for(int i=0;i<num;i++) { if(b[i][0]>center) { center=b[i][1]; result++;//需要增加一个雷达 } } return result; } int main(void) { int dot[100][2],d,num,times=0;//times表示有几个case int answer[100]; for(int i=0;i<100;i++)//初始化 for(int j=0;j<2;j++) dot[i][j]=0; cin>>num>>d; while(d!=0||num!=0) { for(int i=0;i<num;i++) cin>>dot[i][0]>>dot[i][1]; sort_com(dot,num); answer[times]=select_dot(dot,d,num); times++; cin>>num>>d; } for(int i=1;i<=times;i++) cout<<"Case "<<i<<": "<<answer[i-1]<<endl;//输出 return 0; } poj 显示Running time 的错误过不了，求助
ACM北大POJ_1376代码提交一直WA，求大神看看哪里错了？呜呜
---------- #include <iostream> #include <cstring> #include <queue> using namespace std; bool Map[55][55]; bool vis[55][55][4]; //[4] 四个directions，坐标和方向都相同时不能同时经过该点两次； int M,N; bool flag=false; //找到路径置为true； typedef struct { int x,y; //坐标； int time; //走到当前格子所用时间； int dir; //当前格子所朝方向； }point; point Start,End; bool canPass(int x,int y,int direction) { if(x<=0||x>=M||y<=0||y>=N) //走到边界； return false; if(vis[x][y][direction]|| !Map[x][y]|| !Map[x+1][y]|| !Map[x][y+1]||!Map[x+1][y+1]) return false; else return true; } void bfs() { point temp,temp1; queue <point> q; while(!q.empty()) //调用完后要清空队列； q.pop(); int dir1,dir2; q.push(Start); vis[Start.x][Start.y][Start.dir]=true; while(!q.empty()) { temp=q.front(); q.pop(); if((temp.x==End.x)&&(temp.y==End.y)) //到达终点； { flag=true; cout<<temp.time<<endl; return; } dir1=(temp.dir+1)%4; //0为south，1为east，2为north，3为west，每次转90度刚好dir+1或dir-1对4取余即可 dir2=(temp.dir-1+4)%4; temp1=temp; if(!vis[temp1.x][temp1.y][dir1]) //相同点不同方向没有访问过则入队； { vis[temp1.x][temp1.y][dir1]=true; temp1.dir=dir1; temp1.time++; q.push(temp1); } temp1=temp; if(!vis[temp1.x][temp1.y][dir2]) { vis[temp1.x][temp1.y][dir2]=true; temp1.dir=dir2; temp1.time++; q.push(temp1); } for(int i=0;i<3;i++) //走一步，两步，三步的情况全部进栈； { switch(temp.dir) { case 0: temp.x++; break; case 1: temp.y++; break; case 2: temp.x--; break; case 3: temp.y--; break; } if(!canPass(temp.x,temp.y,temp.dir)) break; else { vis[temp.x][temp.y][temp.dir]=true; if(i==0) temp.time++; //走1,2,3步都只需要耗时1秒,只需要第一次走一步时间加1就行； q.push(temp); } } } } int main() { int t; string s; while(cin>>M>>N&&(M||N)) { memset(Map,false,sizeof(Map)); memset(vis,false,sizeof(vis)); flag=false; for(int i=1;i<=M;i++) { for(int j=1;j<=N;j++) { cin>>t; Map[i][j]=t==0?true:false; //true(0)表示可以通行，false(1)表示不能走； } } cin>>Start.x>>Start.y>>End.x>>End.y; cin>>s; if(!canPass(Start.x,Start.y,Start.dir) ||!canPass(End.x,End.y,End.dir)) { cout<<"-1"<<endl; continue; //起始点和终点如果在边界或本身是障碍物则直接输出-1返回； } if(s=="south") Start.dir=0; else if(s=="east") Start.dir=1; else if(s=="north") Start.dir=2; else if(s=="west") Start.dir=3; bfs(); if(flag==false) cout<<"-1"<<endl; } return 0; }
poj 2058算法题Word Encoding完整代码

Catch the cow(POJ3278) 编译器上没问题, OJ上一直runtime error?
[原题网址](http://poj.org/problem?id=3278 "Catch the cow") 下面是我已经在编译器上通过的代码,但是OJ上始终会RE (使用的是广度优先搜索的方法) ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100000 int n, k, ans; int que[MAX_N+10][2]; int vis[MAX_N+10]; int head, tail; void bfs( int x); void enqueue ( int x, int time); int main(void) { scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n); } printf("%d\n", ans); return 0; } void bfs( int x) { enqueue(x, 0); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; nowtime = que[head][1]; head ++; if( nowx == k) { ans = nowtime; break; } for( i=1; i<=3; i++) { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1); vis[nowx*2] = 1; } } } } void enqueue( int x, int time) { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 一开始查了之后说可能是什么栈空间不够,就尝试了一下动态分配空间 (萌新还没学指针,就在网上照猫画虎贴了进去), 但是数字只要大一点程序就无法输出结果 更改后的代码如下: ``` #include <stdio.h> #include <stdlib.h> #define MAX_N 100001 int n, k, ans; //int que[MAX_N+10][2]; /*之前的方案,但同样RE了,可能是空间不足(?),所以尝试如下动态分配的方法*/ //int vis[MAX_N+10]; int head, tail; void bfs( int x, int **que, int *vis); void enqueue ( int x, int time, int **que); int main(void) { int **que; int i, j; int *vis; que = (int**)malloc(sizeof(int*)*MAX_N); //为两个数组分配空间 for( i=0; i<MAX_N; i++) { que[i] = (int*)malloc(sizeof(int)*2); } vis = (int*)malloc(sizeof(int)*MAX_N); scanf("%d %d", &n, &k); if( n>k) { ans = n-k; } else { bfs(n, que, vis); //进入深搜 } printf("%d\n", ans); return 0; } void bfs( int x, int **que, int *vis) { enqueue(x, 0, que); vis[x] = 1; while(head<tail) { int i, nowx, nowtime; nowx = que[head][0]; //队列数据的取出 nowtime = que[head][1]; head ++; if( nowx == k) //结束条件 { ans = nowtime; break; } for( i=1; i<=3; i++) //对三种可能进行遍历 { if( i==1 && vis[nowx-1]!=1 && nowx-1>=0 && nowx-1 <= MAX_N) { enqueue( nowx-1, nowtime+1, que); vis[nowx-1] = 1; } if( i==2 && vis[nowx+1]!=1 && nowx+1>=0 && nowx+1 <= MAX_N) { enqueue( nowx+1, nowtime+1, que); vis[nowx+1] = 1; } if( i==3 && vis[nowx*2]!=1 && nowx*2>=0 && nowx*2 <= MAX_N) { enqueue( nowx*2, nowtime+1, que); vis[nowx*2] = 1; } } } } void enqueue( int x, int time, int **que) //队列数据的写入 { que[tail][0] = x; que[tail][1] = time; tail ++; } ``` 请教一下大佬们上面RE的原因到底是什么, 还有下面的动态分配有什么问题,感激不尽

poj1465 WA 较怪 求解

POJ 1011 Sticks (dfs) 我照着题解敲的，哪位大佬看看为什么WA了
[code=c]#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int v[70]; int a[70]; int n; int ans; int dfs(int index, int sum)//下标和当前木棒长度的总和 { sum += a[index]; int l=sum; if (sum == ans)return l;//找到就返回 if (sum > ans)return l;//大了就说明选择的这根木棒不对 返回 for (int i = index + 1; i < n; i++)//将所以可以选择的木棒枚举一遍 { if (v[i] == 0) { v[i] = 1; l=dfs(i, sum); if (l>ans)//大了就找下一个 { v[i] = 0; while (1)//去除与这个长度相等的木棒 因为肯定也不满足 { if (a[i + 1] != a[i])break; i++; } } else if (l < ans) { return l; }//如果长度不够 就直接结束dfs 因为后面的木棒长度更小 永远也得不到结果 else return l;//找到了 就退出dfs } } return l; //枚举完了长度还不够 退出dfs } bool cmp(int a, int b) { return a > b; } int main() { while (cin >> n) { if (n == 0)break; int k=0; for (int i = 0; i < n; i++) { cin >> a[i]; k+=a[i]; //所有的和 作为结束的条件 } sort(a, a + n, cmp);//从大到小排序 for (ans = a[0];ans<k; ans++)//结果一定不小于最长的木棒 { bool flag = true;//判断是否找到循环退出的条件 memset(v, 0, sizeof(v));//每次没找到都要置零 for (int j = 0; j < n; j++)//把每个木棒遍历一遍是否能找到答案 { if (v[j] == 0) { v[j] = 1; if (dfs(j, 0) != ans) { flag = false; break; }//如果不对就退出这个循环 看下一个结果是否正常 } } if (flag == true)break; } cout << ans << endl; } return 0; }[/code]

poj2488 样例过了为什么还是WA？？？有人帮忙看一下吗？
```.c poj2488 样例过了为什么还是WA？？？ ``` 有人帮忙看一下吗？ ```.c #include <stdio.h> #include <stdlib.h> #define max 30 struct pos { int x; int y; int flag; }map[max][max],res[max]; int n,m,num,cnt=1; int l=1; int dx[9]={-2,-2,-1,-1,1,1,2,2}; int dy[9]={-1,1,-2,2,-2,2,-1,1}; void dfs(int x, int y) { if(l==0) return; int i,nx,ny,flag=0; for(i=0; i<9; i++) { nx=x+dx[i]; ny=y+dy[i]; if(nx<=n && nx>=1 && ny<=m && ny>=1 && map[nx][ny].flag==1 )//&&(dy[i]==1||dy[i]==-2))//保证字典序 { flag=1; cnt++; map[nx][ny].flag=0; res[cnt].x=nx; res[cnt].y=ny; dfs(nx,ny); cnt--; map[nx][ny].flag=1; } } //if(flag==0)//无路可走 //{ if(cnt==n*m) { l=0; printf("Scenario #%d:\n",3-num); for(i=1; i<=n*m; i++) { printf("%c%d",'A'+res[i].y-1,res[i].x); } printf("\n"); if(num!=0) printf("\n"); } return; //} } int main() { int i,j; scanf("%d",&num); while(num--) { scanf("%d %d",&n,&m); l=1; res[cnt].x=1,res[cnt].y=1; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { map[i][j].flag=1; //map[i][j].x=i; } } map[1][1].flag=0; dfs(1,1); if(l==1)//impossible { printf("Scenario #%d:\n",3-num); printf("impossible\n"); if(num!=0) printf("\n"); } } return 0; } ```
poj2159求助 关于字符串的输入问题

RT 链接： [点击打开](http://poj.org/problem?id=3309 "")
poj 1226我的代码为什么wa，求hack，给出测试数据，或者思路的错误

ACM一道题 poj3523 UVA1601双向广度优先BFS

poj 1363 线上指导+源代码
poj 1363 线上指导+源代码，最好有注释，并详细跟我解释~

Java学习的正确打开方式

linux系列之常用运维命令整理笔录

Python 基础（一）：入门必备知识

Python十大装B语法
Python 是一种代表简单思想的语言，其语法相对简单，很容易上手。不过，如果就此小视 Python 语法的精妙和深邃，那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点，并附上详细的实例代码。如能在实战中融会贯通、灵活使用，必将使代码更为精炼、高效，同时也会极大提升代码B格，使之看上去更老练，读起来更优雅。 1. for - else 什么？不是 if 和 else 才

2019年11月中国大陆编程语言排行榜
2019年11月2日，我统计了某招聘网站，获得有效程序员招聘数据9万条。针对招聘信息，提取编程语言关键字，并统计如下： 编程语言比例 rank pl_ percentage 1 java 33.62% 2 c/c++ 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7

SQL-小白最佳入门sql查询一

“狗屁不通文章生成器”登顶GitHub热榜，分分钟写出万字形式主义大作

《程序人生》系列-这个程序员只用了20行代码就拿了冠军