众所周知，在各大计算机竞赛的赛场上，总会有那么一样东西令人头疼，令暴力爆零，令搜索欲哭无泪；在各大在线评测系统上，总会有那么三个字母教 n2n^2 失败，教 2n2^n 无奈，教 n!n! 一个点都拿不到。没错，那就是 T-L-E。

今天就来分享分享怎么避免这三个大字的出现。

正文

卡时，顾名思义，就是卡时间，用尽时间限制中的每一微秒，搜索的话就算没搜完，把局部最小值输出至少有可能 A，当然如果你的算法太差也顶多只能把 TLETLE 变成 WAWA

那么开始吧！

1.代码

直接放代码：（递归同理我就不再放一遍了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#include<ctime>
using namespace std;
#define re register

int main() {
    for (re int i = 0; ; ++i){
        if (i >= 500000000 && 
            i % 1000000 == 0 && 
            clock() >= 990) {
            
            printf("How many done: %d\n", i);
            printf("Time used: %.6lf\n", (double) clock() / CLOCKS_PER_SEC);
            /*在这里输出“正解”*/
            exit(EXIT_SUCCESS);
        }
        /*在这里放程序的主体*/ 
    }
}
2.讲解

  1. #include<cmath>

    头文件记得加上

  2. "if (i >= 500000000 && i % 1000000 == 0 && clock() >= 990)"

    重点！

    • i >= 500000000

    ​ 500000000500000000 是你估计的该循环体能在规定时间能执行的次数，往小估计一点！不然程序来不及判断 clock() >= 990 就超时了。

    • i % 1000000 == 0

    ​ 因为 clock 函数的常数很大，尽量少是执行他， 所以加这个来减少 clock() 的执行次数， 10000001000000 这个数别设太大，不然也容易没卡住而超时。

    • clock() >= 990

    ​ 整个卡时中最重要的部分，注意两点：一、990 这个数字取决于操作系统，因为 WindowsWindows 的 CLOCKS_PER_SEC 是 10001000 , LinuxLinux 下是 10000001000000 ，也就是 WindowWindow 的 clock() 返回值单位为毫秒， LinuxLinux 是微秒，也就是说这个卡时程序要是在 LinuxLinux 上测 990990 应该为 990000990000。**二、**不要太贪了， 11 秒的题开个 980000980000 就行了，可别真开到开 10000001000000。

    • 关于三者的顺序

    ​ 我们知道，几个 && 或 || 隔开的语句顺序不一样可能会有不同的结果，因为如果计算机通过靠前的语句能判断整个语句的布尔值就不会执行后面的，（如 && 之间出现 false , || 之间出现 true ），所以，我们应该将耗时少的判定放在前面，耗时 >= << % << clock()，所以我们按这个顺序放置。否则，卡时的耗时甚至要比搜索本身耗时高，得不偿失。

  3. exit(EXIT_SUCCESS)

    • “相当于 return 0 ，与 return 0 不同的是，无论他在哪执行（包括除 main 以外的函数），整个程序立即结束。依靠递归的搜索不能用 return 0 来停止，需要用它。
3.结果