算法设计与分析上机作业
poj2299 1:Ultra-QuickSort2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<set> #include<map> #include<deque> #include<ctime> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 2000000000 #define ll long long using namespace std; int n; int a[500005], tmp[500005]; ll mergeSort(int l, int r) { if(l == r)return 0; int mid = (l + r) >> 1; ll ans = 0; ans = mergeSort(l, mid) + mergeSort(mid + 1, r); int p1 = l, p2 = mid + 1, p = l; while(p <= r) { if(p2 > r || (p1 <= mid && a[p1] < a[p2])) tmp[p++] = a[p1++]; else { tmp[p++] = a[p2++]; ans += (mid - p1 + 1); } } for(int i = l; i <= r; i++) a[i] = tmp[i]; return ans; } int main() { while(scanf("%d", &n) != EOF) { if(!n)break; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); printf("%lld\n", mergeSort(1, n)); } return 0; } |
2:最近点对问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<set> #include<map> #include<deque> #include<ctime> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 10000000000 #define ll long long using namespace std; int n; struct data{ double x, y; friend bool operator < (data a, data b){ return a.y < b.y; } }a[200005], tmp[200005]; bool cmpx(data a, data b){ return a.x < b.x; } double dis(data a, data b){ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double solve(int l, int r) { if(l == r)return inf; int mid = (l + r) >> 1; int lx = a[mid].x; double ans = min(solve(l, mid), solve(mid + 1, r)); int p1 = l, p2 = mid + 1, p = l; while(p <= r) { if(p2 > r || (p1 <= mid && a[p1] < a[p2])) tmp[p++] = a[p1++]; else tmp[p++] = a[p2++]; } p = l; for(int i = l; i <= r; i++) { a[i] = tmp[i]; if(abs(a[i].x - lx) < ans) tmp[p++] = a[i]; } for(int i = l; i < p; i++) for(int j = 1; j <= 12 && i + j < p; j++) ans = min(ans, dis(tmp[i], tmp[i + j])); return ans; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y); sort(a + 1, a + n + 1, cmpx); printf("%.3lf\n", solve(1, n)); return 0; } |
exercise 2.12 3:集合求交
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<set> #include<map> #include<deque> #include<ctime> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 10000000000 #define ll long long using namespace std; map<int, int>mp; int n, m, ans; int main() { scanf("%d%d", &n, &m); int x; for(int i = 1; i <= n; i++) { scanf("%d", &x); mp[x] = 1; } for(int i = 1; i <= m; i++) { scanf("%d", &x); if(mp[x])ans++; } printf("%d\n", ans); return 0; } |
Subscribe