Hexo
0%

Posted on In ,
Symbols count in article: 2.4k Reading time ≈ 2 mins.

二分

找最大

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//check中的mid符合条件包含
        else r = mid - 1;
    }
    return l;
}
//有可能不存在，需要特判一下是否存在.

找最小

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;//check中的mid符合条件包含
        else l = mid + 1;
    }
    return l;
}
//有可能不存在，需要特判一下是否存在.

1.杨辉三角

在杨辉三角中给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数。

杨辉三角除了几何模型上的数关系外，每一行都是排列组合的结果，通过这个来查找某一行某一列的数的大小，由于题目数据比较大，则采用二分查找降低时间复杂度

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
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <iostream>
# include <functional>
using namespace std;
#define LL long long
const int maxn=1e8;

LL int node(LL int q,LL int p)//输出第q行第p列的值的大小
{
    LL int sum=1;
    for(int i=q;i>=q-p+1;--i)
    {
      sum*=i;
    }
    for(int j=1;j<=p;++j)
    sum/=j;
    return sum;
}

LL int jie(int k)//算出前面有几个数（也可以用等差数列公式）
{
    LL int zong=0;
    for(int i=1;i<=k;++i)
    zong+=i;
    return zong;
}
int main()

{
    int n;
    cin>>n;
    int sum=0;
    if(n==1)
    cout<<1<<endl;//特殊情况
    else{
        for(int i=20;i>=0;--i)//对每一列进行查找
        {
            int l=2*i;
            int r=n;
            while(l<=r)//二分查找
            {
                int mid=(l+r)>>1;
                LL int o=node(mid,i);
                if(o==n)
                {
                    sum=1;
                    cout<<jie(mid)+i+1<<endl;
                    break;
                }
                else if(o>n)//大了的话行数变小
                {
                    r=mid-1;
                }
                else//行数变大
                l=mid+1;
            }
            if(sum==1)
            break;
        }
    }
}

2.wyh的物品

Read more »

Posted on In , ,
Symbols count in article: 767 Reading time ≈ 1 mins. 
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
/*
 * @Author: CrayonXiaoxin
 * @Date: 2023-12-13 20:31:58
 * @LastEditors: Do not edit
 * @LastEditTime: 2023-12-20 19:47:20
 * @FilePath: \c++\code\C.cpp
 */
#include<iostream>
using namespace std;
#define ll long long int
const int maxn = 2e5+10;
int a[maxn];
int n;
void solve()
{
    for (int i = 0; i < n;++i)
        cin >> a[i];
    for (int i = 1; i < n;++i)
    {
        int tem = a[i];
        int now = i;
        while(now>=1)
        {
            if(a[now-1]>tem)
            {
                a[now] = a[now-1];
                now--;
            }
            else
            {
                break;
            }
        }

        a[now] = tem;
        for (int i = 0; i < n;++i)
        {
            cout << a[i] << " ";
        }
        cout << "\n";
    }
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    while(cin>>n)
        solve();
        return 0;
}
Read more »

Posted on In , ,
Symbols count in article: 545 Reading time ≈ 1 mins.

选择排序

  • 从原始数组中选择最小的一个数据，将其和位于第一个位置的数据交换
  • 不断重复
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
#include<iostream>
using namespace std;
#define N 10
 
void Select_Sort(int* arr, int n)   //arr为数据数组，n为数组长度
{
	for (int i = 0; i < n-1; i++) {
		int min = i;
		for (int j = i; j < n; j++) {
			if (arr[min] > arr[j]) {
				min = j;
			}
		}
		if (min != i) {
			swap(arr[i], arr[min]);
		}
	}
}
 
int main()
{
	int arr[N]= { 1,4,6,3,0,2,5,9,8,7 };
	Select_Sort(arr, 10);
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << ",";
	}
	cout << endl;
	return 0;
}
Read more »

Posted on In , ,
Symbols count in article: 1k Reading time ≈ 1 mins.

希尔排序

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

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
/*
 * @Author: CrayonXiaoxin
 * @Date: 2023-12-13 20:31:58
 * @LastEditors: Do not edit
 * @LastEditTime: 2023-12-20 19:37:55
 * @FilePath: \c++\code\C.cpp
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 2e5+10;
int a[maxn];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n;++i)
        cin >> a[i];
    int gap = n;
    while(gap > 1)
    {
        gap /= 2;
        for (int i = 0; i < n - gap;++i)
        {
            int end = i;
            int tem = a[end + gap];
            while(end>=0)
            {
                if(tem>a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tem;
        }    
        for (int i = 0; i < n-1;++i)
        cout << a[i] << " ";
        cout << a[n - 1];
        cout << "\n";
    }


   
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        solve();
        cout << "\n";
    }
        return 0;
}
Read more »

Posted on In , ,
Symbols count in article: 1k Reading time ≈ 1 mins. 
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
/*
 * @Author: CrayonXiaoxin
 * @Date: 2023-12-13 20:31:58
 * @LastEditors: Do not edit
 * @LastEditTime: 2023-12-27 19:35:29
 * @FilePath: \c++\code\C.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 2e5 + 10;
int a[maxn];
int n;

void quickSort(int left, int right)
{
    if (left >= right)
        return;
    int temp = a[left];
    int i = left;
    int j = right;
    while (i < j)
    {
        while (a[j] >= temp && i < j)
        {
            j--;
        }
        swap(a[i], a[j]);
        while (a[i] <= temp && i < j)
        {
            i++;
        }
        swap(a[i], a[j]);
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
    quickSort(left, i - 1);
    quickSort(i + 1, right);
    return;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    if(n==1)
        return;
    quickSort(1, n);
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}
Read more »