概述

以前对于对拍感觉不是很必要，但是今天在刷二分题目的时候对于二分的边界一直都不是很懂。所以在思考如何考虑这个问题的时候，想到另辟蹊径。既然我自己不知道二分是不是写对了，就让电脑来让我判断。所以我决定去网上学习对拍。

但是网上的对拍虽然可以实现判断程序的对错，但是却不能给出确切的每个程序的运行时间。在网上找的一些是用了clock()函数，然而这在程序中引入system()函数时，无法判断system()函数的运行时间，说人话就是clock()函数只能判断该程序中的函数的运行速度，运行其他程序的函数的时间不计算在时间内。所以我又找了许久，终于找到了一个勉强能用的函数gettimeofday

这个函数会计算从1970年1月1日00:00到现在的时间跨度(受不同时区影响)，函数的具体使用方式不是文章的主题，就先不赘述了。（事实是我这个蒟蒻不会写）

实现方法:

以洛谷P1102这道二分题为例。

暴力程序:

#include <iostream>
using namespace std;
long long c[200010];
long long d;
int main(){
	long long a,b;
	scanf("%lld%lld",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%lld",&c[i]);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(c[i]-c[j]==b) d++;
		}
	}
	printf("%lld",d);
	return 0;
}

标程：

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;
long long n,c,a[200010],ans=0;
int main(){
	scanf("%lld%lld",&n,&c);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		int l=1,r=n,j=a[i];
		while(l<r){
			int mid=(l+r)>>1;
			if(a[i]-a[mid]<=c){
				r=mid;
			}
			else l=mid+1;
		}
		int l1=1,r1=n;
		while(l1<r1){
			int mid=(l1+r1)>>1;
			if(a[i]-a[mid]>=c){
				l1=mid+1;
			}
			else r1=mid;
		}
		ans+=l1-l;
	}
	printf("%lld",ans);
	return 0;
}

造数据：

#include <bits/stdc++.h>
#include <sys/timeb.h>
using namespace std;
const int mod=5e4; //数据大点可以发现明显超时，开小点就做个示范看看运行时间。
const int m1=1e3;
int main(){
        struct timeb timer;
        ftime($timer);
	srand(timer.time*1000+timer.millitm); // c++输出毫秒级随机数，不加这一行就会生成全部一样的数
	int n=rand()%mod+1;
	int m=rand()%m1;
	printf("%d %d ",n,m);
	for(int i=1;i<=n;++i){
		printf("%d ",rand()%m1);
	}
	return 0;
}

用来对拍的程序：

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
int main(){
	struct timeval s1,s,e; //这个函数的格式就是这样
	int t1,t2;
	for(int i=1;i<=1000;++i){
		system("./make >date.in");//重定向输出
		gettimeofday(&s1,NULL);
		system("./b <date.in >1.out"); //重定向输入输出
		gettimeofday(&s,NULL);
		system("./baoli <date.in >2.out");//重定向输入输出
		gettimeofday(&e,NULL);
		t1=(s.tv_sec-s1.tv_sec)*1000+(s.tv_usec-s1.tv_usec)/1000; //把时间转化成毫秒
		t2=(e.tv_sec-s.tv_sec)*1000+(e.tv_usec-s.tv_usec)/1000; //把时间转化成毫秒
		if(system("diff 1.out 2.out")){
			puts("WA");
			return 0;
		}
		else printf("AC,test point #%d,btime %dms ,baotime %dms\n",i,t1,t2);
                                   //分别输出数据的组数，第一个程序的运行时间，第二个程序的运行时间。
	}
}

自动编译加运行的bash脚本：

g++ biao.cpp -o biao
if [ $? -eq 0 ]
then
	g++ bao.cpp -o bao
	if [ $? -eq 0 ]
	then
		g++ shujv.cpp -o shujv
		if [ $? -eq 0 ]  
			g++ pai.cpp -o pai
			then
				./pai
		fi
	fi
fi			

总结

大体上就是这样的，希望看到这篇文章的人以后二分再也不用担心