3.18算协讲课

  1. Problem Description
  2. Lower_bound && Upper_bound
  3. 偶达奇不达
  4. 代码规范
  5. 素数筛法

Problem Description

My birthday is coming up and traditionally I’m serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input
One line with a positive integer: the number of test cases. Then for each test case:
—One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends.
—One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.

Output
For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).

Sample Input
3 3 3 4 3 3 1 24 5 10 5 1 4 2 3 4 5 6 5 4 2

Sample Output
25.1327 3.1416 50.2655

翻译: 主人家里来了F个他的朋友，他家里有n个Pie，主人希望把Pie分出F+1份，体积相同（包括主人），所有的Pie不需要都分完，问你每个人最大能分到多大体积的Pie。

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
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
double pie[10001];
int n,f;

bool cmp (double a,double b) {
    return a > b;
}

bool fun (double num) {
    int cnt = 0;
    int tmp = 0;
    for (int i = 0; i < n; i++) {
        tmp = (int)(pie[i] / num);
        if (tmp == 0 || cnt >= f)
            break;
        cnt += tmp;
    }
    return cnt < f ? false : true;
    
}

int main () {
    int t;
    double l,r,mid;
    cin >> t;
    while (t--) {
        cin >> n >> f;
        f++;
        for (int i = 0; i < n; i++) {
            cin >> pie[i];
            pie[i] = pi * pie[i] * pie[i]; //计算每个pie的体积
        }
        sort (pie, pie + n, cmp);
        l = 0;
        r = pie[0];
        mid = (l + r) / 2;
        while (r > l) {
            if (fun (mid))
                l = mid;
            else
                r = mid;
            mid = (l + r) / 2;
        }
        printf("%.4f\n",mid);
    }
    return 0;
}

Lower_bound && Upper_bound

lower_bound: 在升序数组中在[left,right)区间内二分查找元素m.返回该值在数组中的下标.

特殊情况:

1.如果m不存在,那么返回第一个比该值大的数的坐标.

2.如果m比区间内所有数都大,那么返回left.这个时候会越界.

3.如果存在多个m,返回第一个m的下标.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
int a[1000010],t,n,l,r;  
int main() {  
     
    cin >> t;
    for(int i = 0; i < t; ++i)  
        cin >> a[i];  
    for(int i = 0; i < t; ++i) {  
        cin >> l >> r >> n;
        cout << lower_bound(a + l, a + r, n) - a) << endl;  
    }  
}

upper_bound: 在升序排列的a数组内二分查找[left,rignt)区间内的值为m的元素.返回m在数组中的下标+1.

特殊情况:

1.如果m不存在,那么返回第一个比m大的数的下标.

2.如果m比区间内所有的数都大,那么返回right.这时会越界.

3.如果存在多个m,返回最后一个m的下标+1.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
int a[1000010],t,n,l,r;  
int main() {  
	cin >> t; 
    for(int i = 0; i < t; ++i)  
        cin >> a[i];
    for(int i = 0; i < t; ++i) {  
        cin >> l >> r >> n;  
        cout << upper_bound(a + l, a + r, n) - a);  
    }  
}

偶达奇不达

一个判断能否从图一点到达另一点的结论.

假设规定时间为ts,从一点到最近一点花费时间为1s,要从某点恰好到达另一点,两点之间可行的最短距离为l.
如果l是偶数且l <= t 那么即可恰好到达,否则无法到达.

代码规范

手动艾特某位同学.

素数筛法

未优化版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long long prime[10000];
bool isprime[10000];

void prime () {
	long long cnt = 1;
	memset (isprime,1,sizeof(isprime));
	isprime[0] = isprime[1] = 0;
	for (long long i = 2; i <= 10000; i++) {
		if(isprime[i]){
			prime[cnt++] = i;
		}
		for (long long j = i * 2; j <= 10000; j += i) {
			isprime[j] = 0;
		}
	}

}

优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long prime[10000];
bool isprime[10000];

void prime () {
	long long cnt = 1;
	memeset (isprime,1,sizeof(isprime));
	isprime[0] = isprime[1] = 0;
	for (long long i = 2; i <= 10000; i++) {
		if(isprime[i])
			prime[cnt++] = i;
		for (long long j = 1; j < cnt && prime[j] * i < MAX; j++) {
			isprime[prime[j] * i] = 0;
		}
	}
}
script>