【練習】
2.3-2 MERGE的改進
void MERGE(int *A, int p,int q, int r) {
int B[maxn] , i = p , j = q+1 , k = 0;
while(k < r - p + 1) {
if(i > q || j <= r && A[i] > A[j]) B[k++] = A[j++];
else B[k++] = A[i++];
}
for(i=0;i<r-p+1;i++) A[p+i] = B[i];
}
2.3-5 二分查找的C++代碼
int find(int *a, int l, int r, int value) {
if(l == r) return l;
int mid = (l+r) >> 1;
if(a[mid] >= value) return find(a, l, mid, value);
else return find(a , mid+1, r , value);
}
*2.3-7 （這道題其實有O(n)的算法，而且寫起來更方便些）這里是O(nlogn)的算法
O(nlogn)算法思想：1.首先進行排序；2.然后枚舉每一個小于等于x/2的數S[i]，二分查找對應的x-S[i]是否存在
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
bool findx(
int *S,
int n,
int x,
int l,
int r) {
if(l > r)
return false;
if(l ==r)
return S[l] == x;
int mid = (l+r) >> 1;
if(S[mid] >= x)
return findx(S, n, x, l, mid);
else return findx(S, n, x, mid+1, r);
}
bool check(
int *S,
int n,
int x) {
for(
int i=0;S[i]<=x/2 && i < n;i++) {
if(findx(S, n, x-S[i], i+1, n-1))
return true;
}
return false;
}
int main() {
int S[1010] , x , n;
while(~scanf("%d%d" , &n , &x)) {
for(
int i=0;i<n;i++) cin >> S[i];
if(check(S, n, x)) puts("yes");
else puts("no");
}
return 0;
}
O(n)的方法是在數的范圍不是特別大的時候（或者數的范圍比較大，此時采用hash的方法）標記的方法，這里假設數的范圍<=10000，并且假設數沒有重復的情況下，其他情況稍許改變一下就行：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
bool check(
int *S,
int n,
int x) {
bool vis[10001] = {0};
for(
int i=0;i<n;i++) vis[x-S[i]] =
true;
for(
int i=0;i<n;i++)
if(vis[S[i]])
return true;
return false;
}
int n ,x , S[maxn];
int main() {
while(~scanf("%d%d" , &n , &x)) {
for(
int i=0;i<n;i++) cin >> S[i];
if(check(S, n, x)) puts("yes");
else puts("no");
}
return 0;
}
2-4（逆序對）：這道題就是在歸并排序中得到逆序對，具體見代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int ans;
void merge_sort(
int *A,
int l,
int r) {
if(l >= r)
return;
int mid = (l+r) >> 1;
merge_sort(A, l, mid);
merge_sort(A, mid+1, r);
int i = l , j = mid+1 ,B[maxn] , k = l;
while(i <= mid || j <= r) {
if(i > mid || j <= r && A[j] < A[i]) B[k++] = A[j++] , ans += mid-i+1;
else B[k++] = A[i++];
}
for(i=l;i<=r;i++) A[i] = B[i];
}
int main() {
int A[maxn] , n;
while(~scanf("%d" , &n)) {
for(
int i=0;i<n;i++) cin >> A[i];
ans = 0;
merge_sort(A, 0, n-1);
cout << ans << endl;
//for(int i=0;i<n;i++) cout << A[i] << " "; cout << endl;
}
return 0;
}
posted on 2015-03-07 15:19
JulyRina 閱讀(323)
評論(0) 編輯 收藏 引用 所屬分類:
算法專題