a

a

a

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';

            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                // 保护防止 mid == l时 无线循环 
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }

    return 0;
}
/*

	感悟，算法的思想是当我们找到一个大于等于目标值的点时会保存好这个点 并缩小范围，那么剩下的这个范围内部一定会存在一个target，（如果mid 比target小则不回舍弃原点如果大则证明可以缩小）这回导致我们的范围最后唯一且我们必须保证最后一个元素大于等于target因为缩小的范围尽可能靠左得到的便是左节点
    
    
比较好理解的版本如下 ：
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n,m;
	cin>>n>>m;
	int num[n];
	for(int i=0;i<n;i++){
		cin>>num[i];
	}	
	while(m--){
		int target;cin>>target;
		int l = 0,r = n - 1;
		while(l < r){
			int mid = (l + r) >> 1;
			if (num[mid] == target) {
				r = mid;
			} else if(num[mid] > target) {
				r = mid - 1;
			}
			 else {
				l = mid + 1;
			}
		}
		if (num[r] == target) cout<<l<<" ";
		else {
			cout<<"-1 -1"<<endl;
			continue;
		}
		l = 0, r = n - 1;
		while(l < r){
			int mid = (l+r + 1) >>1;
			if (num[mid] == target) {
				l = mid;
			} else if (num[mid] > target) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}  
		cout<<l<<endl;
	}
}


题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个浮点数 n
，求它的三次方根。

输入格式
共一行，包含一个浮点数 n
。

输出格式
共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6
 位小数。

数据范围
−10000≤n≤10000

个人的垃圾代码

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
62
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int getDevi(int i) {
	int ans = 1;
	while(i--){
		ans *= 10;
	}
	return ans;
}
int main () {
	double num;
	int flag = 1;
	scanf("%lf",&num);
	if (num < 0) {
		num *= -1;
		flag = -1;
	} 
	
	//防止负数的情况 
	double res = 0;
	
	
	int left = 0;
	int right = num + 1;
	
	while(left < right){
		ll mid = (left + right + 1)>>1;
	// 防止越界的情况
    	if (mid * mid * mid <= num) {
			left = mid;
		} else {
			right = mid - 1;
		}
	}
	res += left;
	
	
	for(int i=1;i<=6;i++){
		left = 0;
		right = 9;
		while(left < right){
			int mid = (left + right + 1) >>1;
			double get = res + (1.0 * mid / getDevi(i));
			
			if (get * get * get == num) {
				break;
			} else if (get * get *get > num) {
				right = mid - 1;
			} else {
				left = mid;
			}
		}
		res += 1.0*left/getDevi(i);
	}
	printf("%.6f",res*flag);
}

/*
对于数据范围理解不够透彻导致在，定义上出现了越界的情况，同时对于范围的把握也不到位应该取更小的值for(int i=1;i<=6;i++){ 这里保留六个小数我们应该更加深入同时没有办法将技巧泛化导致回答问题沉余

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
        // 假设mid = left 意味着right = left 所以这里不必考虑边界值的问题
    }

    printf("%.6lf\n", l);
    return 0;
}