IPUOJ 首页 小测 习题 比赛 评测 进度 讨论 帮助
登录
讨论
全局板块

【10503 排座椅】求助：结果是WA与RE，求DEBUG

mildjack 2019-08-14 13:52:42 2019-12-16 13:44:57

这是一份提问帖的模板，发帖提问请参考本贴的格式。

我的思路

扫描所有行和列，取最大的 K 行和 L 列作为答案。

我的代码

#include <cstdio>
#include <algorithm>

int M,N,K,L,D;
const int Max = 1000 + 5;
struct Line{
	int cnt,Id;
#ifdef DEBUG
	void print() {
		printf("(cnt:%d Id:%d)",cnt,Id);
	}
#endif
};

bool cmp (const Line& a,const Line& b) {
		if (a.cnt > b.cnt)
			return true;
		else if (a.Id < b.Id)
			return true;
		else return false;
}
	
Line A[Max],B[Max];				//添加的效率 A :行;B : 列  
/*1 means who will spaek 
0  0 0 0 0 
1  1 0 0 0
  |
  |
  A[0]++
  
0 0 0 0 0 
0 0 0 0 1>>B[2]++ 
0 0 0 0 1
.
.
.
*/ 

#ifdef DEBUG
void dp(Line* a,int n) {
	for (int i = 0;i < n; ++i)	a[i].print();
	puts("};");
}
#endif

int main() {
#ifdef DEBUG
	freopen("in.txt","r",stdin);
#endif
	scanf("%d%d%d%d%d",&M,&N,&K,&L,&D);
	for (int i = 0;i < D; ++i) {
		int x,y,p,q; 							// in text says X Y P Q
		scanf("%d%d%d%d",&x,&y,&p,&q);
		if (x != p){
			A[x - 1].cnt++;
			A[x - 1].Id = x;
#ifdef DEBUG
	printf("A:{");
	dp(A,M);
#endif
		} else {
			B[x - 1].cnt++;
			B[x - 1].Id = x;
#ifdef DEBUG
	printf("B:{");
	dp(B,N);
#endif
		}
	}
	
#ifdef DEBUG
	printf("A:{");
	dp(A,M);
#endif
	
#ifdef DEBUG
	printf("B:{");
	dp(B,N);
#endif
	// reading finally
	
	std::sort(A,A + M,cmp);
	
#ifdef DEBUG
	printf("A:{");
	dp(A,M);
#endif

	std::sort(B,B + N,cmp);
	
#ifdef DEBUG
	printf("B:{");
	dp(B,N);
#endif
	
	// the beginning
	
	// for Down
	
	for (int i = 0;i < K; ++i)	printf("%d ",(A + i)->Id); 
	puts("");
	
	//for Line
	
	for (int i = 0;i < L; ++i)	printf("%d ",(B + i)->Id);	
	
	// DONE
	return 0;
}

我的问题

我的评测结果是 1-3 和 5 测试点结果为 WA，其余的测试点结果为 RE。
我觉得问题出在 cmp 函数上面。
（最好说明自己做过什么，比如：）我加了一些 ifdef 调试语句，但是自己没看出问题来，请问：

  1. 我的代码哪里有问题？
  2. 以后遇到同类问题，我要用什么方法能比较好地找出 bug ？

共 4 条回复

mildjack
2019-08-16 13:08:52

我的问题

问题1

11231312

问题2

124345345

if (x != p){
	A[x - 1].cnt++;
	A[x - 1].Id = x;
} else {
	B[x - 1].cnt++;
	B[x - 1].Id = x;
}
tumd
2019-08-14 21:14:57

#【10503 排座椅】求助：求DEBUG

###此文为回复mildjack的评论。

我的思路

  • 排序所有行和列
  • 扫描所有行和列，取最大的K行和L列作为答案。

##我的代码



#include <cstdio>
#include <cmath>
#include <algorithm>

const int M = 1000 + 5;
struct Pair {
	int cnt,Id;
	bool operator< (const Pair& b) const {
		if (!(cnt <= b.cnt))
			return true;
		else if (Id < b.Id)
			return true;
		return false;
	}


#ifdef DEBUG
	void print() {
		printf("(cnt:%d Id:%d)",cnt,Id);
	}
#endif
} A[M],B[M];

//A纵	B横;

#ifdef DEBUG
void dp(Pair* a,int n) {
	printf("{");
	for (int i = 0; i < n; ++i)	a[i].print();
	puts("};");
	}
#endif
int main() {
#ifdef DEBUG
	freopen("in.txt" ,"r",stdin);
#endif
	int M,N,K,L,D;
	scanf("%d%d%d%d%d",&M,&N,&K,&L,&D);

	for (int i = 0; i < D; ++i) {
		int x,y,p,q;
		scanf("%d%d%d%d",&x,&y,&p,&q);
		if (x != p && y == q && abs(x - p) == 1) {			//纵坐标相等;
			if (x > p)	std::swap(x,p);
			A[y - 1].cnt++;										//y-1列标记;
			A[y - 1].Id = y - 1;
#ifdef	DEBUG
			putchar('A');
			dp(A,M);
#endif
		} else {
												//横坐标	相等
			if (y > q)	std::swap(y,q);
			
			B[x - 1].cnt++;										//x-1列标记;
			B[x - 1].Id = x;
#ifdef DEBUG
			putchar('B');
			dp(B,N);
#endif
		}
	}

	// sort

	std::sort(A - 1 ,A + M);
	std::sort(B - 1,B + N);

#ifdef	DEBUG
	dp(A,M);
#endif

#ifdef DEBUG
	dp(B,N);
#endif
	// print

	for (int i = 0; i < K; ++i) {
		printf("%d ",A[i].Id);
	}
	puts("");

	for (int i = 0; i < L; ++i) {
		printf("%d ",B[i].Id);
	}
	puts("");

	return 0;
}

##我的问题

我觉得问题出在 sort 函数上面。 #####所以

  1. 我反复更改sort函数的参数表；
  2. 对前文进行DEBUG；

#最后，我衷心地祝愿老师们对我们的栽培！

Showson
2019-08-14 15:11:01

上周答疑课大部分之间都在介绍如何使用输出进行调试 如果输出调试掌握得不好 可以去看看上周答疑课的内容

mildjack
2019-08-14 14:21:41

首先，这份代码的思路是正确的：我们的目的是找出最大的 K 行和 L 列作为答案。

这个贪心策略完全正确，这是因为我们容易看出：行与行之间的交头接耳，和列与列之间的交头接耳，互相独立不影响。

提问中对自己的 cmp 函数有所怀疑，我们不妨看一下 cmp 函数的内容：

bool cmp(const Line& a, const Line& b) {
    if (a.cnt > b.cnt)
        return true;
    else if (a.Id < b.Id)
        return true;
    else
        return false;
}

优先比较数量，再根据字典序优先的要求比较 id，这符合我们的算法思路，而且没有语法错误，因此，这个函数大概率是没有问题的。

那么，如何知道错误在哪里？这时候一般的做法是寻找一组能卡掉算法的数据。点开评测结果，随便选取一组没通过的数据，比如测试点 2​ ，答案文件是：

1 2 4 5 7 8 9
1 2 4 5 6 7 8 9

而你的程序输出是：

8 4 7 6 0 2 3 
4 9 3 5 8 0 7 1

从这个评测结果可以看出：

  1. 你没有按照要求从小到大输出结果。
  2. 你的结果中输出了 0 ，而根据题目的样例，过道编号应该是从 1 开始的，不应该输出 0 。
  3. 就算解决了上面两个问题，你的结果仍然不正确。

既然连最简单的小规模数据都无法通过，必然是代码实现过程中有非常基础的错误，这种程度的错误应该是能够自己 DEBUG 的。

现在说一下 DEBUG​ 方法：自己构造几组小数据，在纸上画出你构造的数据，再输入相应的值，看程序运行结果是否与预期相符合。如果不符，就利用你实现的 ifdef 来输出中间的所有结果来调试，看哪一步中间结果和你的预期不符。

本题的代码明显有问题，只要你随便尝试了几组数据，甚至直接使用样例，应该都能发现过不了。所以，建议你至少独立思考解决问题，至少把样例通过、把各类小数据通过。这个时候如果还有问题，才是向老师提问的最佳时机。

那么本代码的其中一个问题在哪里呢？可以看到这几行语句：

if (x != p){
	A[x - 1].cnt++;
	A[x - 1].Id = x;
} else {
	B[x - 1].cnt++;
	B[x - 1].Id = x;
}

这几行语句是为了判定行（A）与列（B），如果你真的输出了中间结果来调试你的代码，你会发现你的 A 与 B 数组并不是你期望的值，也就是说，你这几行代码错了。你不能通过 x != p 这一条件来简单地判定两个人是坐在一行的。

这只是其中一个 bug ，如果你按照老师教的方法规范地输出中间结果来 DEBUG ，你应该能自己想明白为什么最终答案有的输出了 0 。如果这个问题你自己思考过后还是没有想出来，可以再向老师提问。

IPUOJ Powered by SYZOJ.