澳门新葡亰平台官网0.0

by admin on 2020年1月20日

大约的主题材料,但自个儿不会

poj 1862 Stripies/优先队列,pojstripies

原题链接:

简易题,贪心+优先队列首要演习一下stl大根堆

写了三种实现情势写成类的花样依然要慢一些。。。

手打的heap:

1:

澳门新葡亰平台官网 1 1
#include<cstdio> 2 #include<cstdlib> 3
#include<cmath> 4 #include<iostream> 5 class Solution{ 6
public: 7 static const int Max_N = 110; 8 int sz; 9 double
heap[Max_N]; 10 inline void init(){ 11 sz = 0; 12 } 13 inline void
push(double x){ 14 int i = sz++; 15 while (i > 0){ 16 int p = (i – 1)
>> 1; 17 if (heap[p] >= x) break; 18 heap[i] = heap[p];
19 i = p; 20 } 21 heap[i] = x; 22 } 23 inline double pop(){ 24 double
ret = heap[0], x = heap[–sz]; 25 int i = 0; 26 while ((i <<
1) + 1 < sz){ 27 int a = (i << 1) + 1, b = (i << 1) + 2;
28 if (b < sz && heap[a] <= heap[b]) a = b; 29 if (heap[a]
<= x) break; 30 heap[i] = heap[a]; 31 i = a; 32 } 33 heap[i] =
x; 34 return ret; 35 } 36 }; 37 int main(){ 38 #ifdef LOCAL 39
freopen(“in.txt”, “r”, stdin); 40 freopen(“out.txt”, “w+”, stdout); 41
#endif 42 int n; 43 double a, b; 44 Solution ans; 45 ans.init(); 46
scanf(“%d”, &n); 47 while (n–){ 48 scanf(“%lf”, &a); 49 ans.push(a); 50
} 51 while (ans.sz > 1){ 52 a = ans.pop(), b = ans.pop(); 53
ans.push(2 * sqrt(a * b)); 54 } 55 printf(“%.3lf”, ans.pop()); 56
return 0; 57 } View Code

2:

澳门新葡亰平台官网 2 1
#include<cstdio> 2 #include<cstdlib> 3
#include<cmath> 4 #include<iostream> 5 struct Node{ 6
static const int Max_N = 110; 7 int sz; 8 double heap[Max_N]; 9
Node() :sz(0){} 10 inline void push(double x){ 11 int i = sz++; 12 while
(i > 0){ 13 int p = (i – 1) >> 1; 14 if (heap[澳门新葡亰平台官网,p] >= x)
break; 15 heap[i] = heap[p]; 16 i = p; 17 } 18 heap[i] = x; 19 }
20 inline double pop(){ 21 double ret = heap[0], x = heap[–sz]; 22
int i = 0; 23 while ((i << 1) + 1 < sz){ 24 int a = (i <<
1) + 1, b = (i << 1) + 2; 25 if (b < sz && heap[a] <=
heap[b]) a = b; 26 if (heap[a] <= x) break; 27 heap[i] =
heap[a]; 28 i = a; 29 } 30 heap[i] = x; 31 return ret; 32 } 33 }ans;
34 int main(){ 35 #ifdef LOCAL 36 freopen(“in.txt”, “r”, stdin); 37
freopen(“out.txt”, “w+”, stdout); 38 #endif 39 int n; 40 double a, b;
41 scanf(“%d”, &n); 42 while (n–){ 43 scanf(“%lf”, &a); 44 ans.push(a);
45 } 46 while (ans.sz > 1){ 47 a = ans.pop(), b = ans.pop(); 48
ans.push(2 * sqrt(a * b)); 49 } 50 printf(“%.3lf”, ans.pop()); 51
return 0; 52 } View Code

3:

澳门新葡亰平台官网 3 1
#include<cstdio> 2 #include<cstdlib> 3
#include<cmath> 4 #include<iostream> 5 const int Max_N =
110; 6 double heap[Max_N]; 7 int sz = 0; 8 void push(double x){ 9 int
i = sz++; 10 while (i > 0){ 11 int p = (i – 1) >> 1; 12 if
(heap[p] >= x) break; 13 heap[i] = heap[p]; 14 i = p; 15 } 16
heap[i] = x; 17 } 18 double pop(){ 19 double ret = heap[0], x =
heap[–sz]; 20 int i = 0; 21 while ((i << 1) + 1 < sz){ 22
int a = (i << 1) + 1, b = (i << 1) + 2; 23 if (b < sz &&
heap[a] <= heap[b]) a = b; 24 if (heap[a] <= x) break; 25
heap[i] = heap[a]; 26 i = a; 27 } 28 heap[i] = x; 29 return ret;
30 } 31 int main(){ 32 #ifdef LOCAL 33 freopen(“in.txt”, “r”, stdin);
34 freopen(“out.txt”, “w+”, stdout); 35 #endif 36 int n; 37 double a,
b; 38 39 scanf(“%d”, &n); 40 while (n–){ 41 scanf(“%lf”, &a); 42
push(a); 43 } 44 while (sz > 1){ 45 a = pop(), b = pop(); 46 push(2
* sqrt(a * b)); 47 } 48 printf(“%.3lf”, pop()); 49 return 0; 50 }
View Code

4:

std::priority_queue<double> ans

澳门新葡亰平台官网 4 1
#include<cstdio> 2 #include<cstdlib> 3
#include<cmath> 4 #include<queue> 5
#include<iostream> 6 int main(){ 7 #ifdef LOCAL 8
freopen(“in.txt”, “r”, stdin); 9 freopen(“out.txt”, “w+”, stdout); 10
#endif 11 int n; 12 double a, b; 13 scanf(“%d”, &n); 14
std::priority_queue<double> ans; 15 while (n–){ 16 scanf(“%lf”,
&a); 17 ans.push(a); 18 } 19 while (ans.size() > 1){ 20 a =
ans.top(), ans.pop(); 21 b = ans.top(), ans.pop(); 22 ans.push(2 *
sqrt(a * b)); 23 } 24 printf(“%.3lf”, ans.top()); 25 return 0; 26 }
View Code

 

1862 Stripies/优先队列,pojstripies
原题链接:
轻巧题,贪心+优先队列首要演习一下stl大根堆
写了二种完结形式写成…

对此指针平昔很迷,明日看了弹指间指针交流数组,知识量少之甚少,希望能支援到我们。

#include<iostream>
#include<conio.h>
using namespace std;

选取指针来沟通数组重假若为了节省时间嘛,有三种沟通方式

int main()
{
    double a=3.3,b=1.1;
    int i=a/b;
    cout<<i<<endl;
    getch();
    return 0;
}

第生机勃勃种是写四个函数把数组传过去接下来用swap沟通,就能够

为什么最终i=2呢

代码如下:

#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[100000050],b[100000050];
void da(int *a,int *b)
{
  swap(a,b);
  cout<<a[1]<<” “<<b[1]<<endl;
}
int main()
{
  double tmp=clock();
  a[1]=1,b[1]=2;
  da(a,b);
  printf(“%.2lf”,(double)((clock()-tmp)/CLOCKS_PER_SEC));
  return 0;
}

但是这么的置换只在函数里有用,到主函数里照旧生机勃勃对大器晚成于还没交流,所以大家还有另生机勃勃种办法

#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
int a[100000050],b[100000050];
int main()
{
double tmp=clock();
a[1]=1,b[1]=2;
int *op1=a;
int *op2=b;
swap(op1,op2);
cout<<op1[1]<<” “<<op2[1]<<endl;
printf(“%.2lf”,(double)((clock()-tmp)/CLOCKS_PER_SEC));
return 0;
}

代码里皆不时光函数,读者能够和蔼运转一向下探底视时间,应该是0.00

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图