算法设计与分析上机作业

#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;
}

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;

}

#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;
}

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;

}

#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;
}

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;

}

hzwer.com _ Home | http://hzwer.com

poj2299 1:Ultra-QuickSort2

2:最近点对问题

exercise 2.12 3:集合求交

分类目录

热门文章

Myfriends

近期评论