挑战程序设计竞赛(一)

算法竞赛的目的

• 设计高效并且正确的算法
• 正确的实现

时间复杂度

时间复杂度在千万左右能接受

三角形组合题

实现代码

#include <iostream>
#include <algorithm>

using namespace std;
int maxN = 105;
int a[105];

int main() {
    int n;
    int maxSum = 0;
    while (cin >> n && n > 0) {
        maxSum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    int sum = a[i] + a[j] + a[k];
                    int maxLen = max(a[i], max(a[j], a[k]));
                    int otherLen = sum - maxLen;
                    if (otherLen > maxLen) {
                        maxSum = max(maxSum, sum);
                    }
                }
            }
        }
        printf("%d\n", maxSum);
    }
    return 0;
}

POJ的题目Ants

如果采用穷竭搜索的方式的话，时间复杂度会非常高。其实我们只要思考，假设两个蚂蚁遇到的时候什么都不发生，那么求最大时间的话，我们只要求蚂蚁到杆子最大的距离就可以。求最短时间的话，我们只用求每只蚂蚁到两端距离中小的，然后求出最大值即可。实现代码：

#include <iostream>
#include <algorithm>

using namespace std;

int a[100005];

int main() {
    int L;
    int n;
    cin >> L >> n;
    int maxT = 0;
    int minT = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maxT = max(maxT, max(a[i], L - a[i]));
        minT = max(minT, min(a[i], L - a[i]));
    }
    printf("min = %d\nmax = %d", maxT, minT);
    return 0;
}

抽签问题的优化

通过二分查找来搜索元素

bool binary_search(int x){
    int l = 0, r = n;
    while(r - l >=1){
        int i = (l+r)/2;
        if(kk[i] == x) return true;
        else if(kk[i]<x) l=i+1;
        else r = i;
    }
    return false;
}

首先将两个数的和求出来，然后在另一部分查询这样就可以优化空间复杂度为n^2logn

int n,m,k[MAX_N];
int kk[MAX_N*MAX_N];
bool binary_search(int x){
    int l = 0;
    int r = n*n;
    while(r - l >=1){
        int i = (l+r)/2;
        if(kk[i] == x) return true;
        else if(kk[i]<x) l=i+1;
        else r = i;
    }
    return false;
}
void solve(){
    // 求出和
    for(int c = 0; c < n;c++){
        for(int d = 0;d<n;d++){
            kk[c*n+d]=k[c]+k[d];
        }
    }
    bool f = false;
    // 排序 方便进行二分搜索
    sort(kk,kk+n*n);
	for(int a = 0;a<n;a++){
        for(int b = 0;b<n;b++){
            if(binary_search(m-k[a]-k[b])){
                f = true;
            }
        }
    }
    if(f)puts("Yes");
    else puts("No");
}