スケジュール

アルゴリズムとは?いかなる問題を解決するために制定された一連のプログラムまたは方法を式化して表現する.
すなわち,アルゴリズムは問題を解決する方法であり,問題を解くパターンである.
ビオ記号法
時間と空間の複雑さを表す漸近表現
最悪の場合を考慮して計算する.
係数を無視して、時間、空間の複雑さで最も影響力のある項で表現します.

空間複雑度
プログラムの実行と完了に必要なストレージ容量.
総空間需要=固定空間需要+可変空間需要S(P)=c+Sp(n)

固定スペース:入力されたスペース要件を考慮しない(定数とみなされる)
可変空間かへんくうかん:入力に関連する(計算アルゴリズムの空間的複雑さ)にゅうりょくにかんけいする(けいさんアルゴリズムの空間的複雑さ)
再帰工場:
空間的複雑度はパラメータ1が入るまで一度に蓄積され,その後終了するのでO(n)
重複工場:
ずっと値を乗じているので、あまりスペースを取らないのでO(1)

時間の複雑さ

は毎秒1億回(=10^8)の演算が可能とする
繰り返し文の合計を求める
繰り返し文を1からnへ、時間複雑度O(n)
ダイレクトライト
一度だけ計算して、O(1)

欲張り法greedyアルゴリズム

単純にすべてのことをするだけでは、時間、空間の複雑さの観点から見ると、効率的ではありません.
すべての選択を考慮せずに、各フェーズで最良の方法のみが選択されます.すなわち、ユーザーは最初からケースのみを考慮します.
この場合、正当性を証明することが重要です.
グリディアルゴリズムはいつも成立しますか?我々が選択した方法のみで探索するので,最適解(実際の正解)は現れないかもしれない.
したがって,グリディアルゴリズムの正当性を証明することが重要である.証明の方法は2つあります.
1.貪欲に選択しても、問題の最適解を見つけることができます.
2.ローカル問題の最適解では、問題全体の最適解を生成することができる.
貪欲な選択属性:各段階で貪欲な選択は常に最適な道の一つに通じている.
最適局所構造(重要):局所問題の最適解では、問題全体の最適解を生成することができる.ほとんどの場合は言うまでもありません.
問題は、どのような方法を選んで正当性を証明するかが難しいことだ.

質問する

1931会議室の手配

最終的には、終了時間は重要な問題です.そのため、終了時間を優先して、会議が終わると次の会議を開始することができます.
会議室の配分問題が最良であり、保障問題であることを証明する.
1.どの会議でも時間が重なる会議を選択できない
残りの会議についても、できるだけ多くの会議を行います.
そのため、これは最適な部分の問題です.
方法を考える
1.開始時間を基準にできません.
2.短い会議をうまく開くこともできない.
3.终わりの时间はよくできます.
帰約法による証明
我々の選択が最適化に達することができず,最適化がPである場合にのみ最適解が存在する選択は望ましくない.
分類法は仮定結論に矛盾があり、仮定に矛盾があることを証明し、結論が本当であることを証明する方法である.
ここでは,終了時間で適切な解答を行うことで最適解を求めることができる.終了時間で問題を解決できない場合は、迅速に開始する会議や短時間の会議を選択する必要があります.このような解答は、最適な会議を求めることはできません.

//입출력 속도 향상
//c문법과 동기화를 멈추겠다.
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

とにかく.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;

int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t = 0;
	vector<pair<int, int>> a(t);
	cin >> t;

	for (int i = 0; i < t; ++i) {
		cin >> a[i].second >> a[i].first;
	}
	sort(a.begin(), a.end());

	int ans = 1;
	pair<int, int> pos = a[0];
	for (int i = 1; i < t; ++i) {
		if (pos.first < a[i].second) {
			ans += 1;
			pos = a[i];
		}
	}
	cout << ans;
}

14659南北の序列を整理してから来ました

こいつに更新を続けて、値段を探せばいい.
ここで重要な点は,PS領域の問題を解決するために多くのグローバル変数を使用することである.通常、グローバル変数は初期化を必要とせずに0に初期化されます.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#define ll long long
#define len 1001
using namespace std;

int ans, big,i;
int main(void) {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t = 0;
	cin >> t;
	vector<int> a(t);
	for (i = 0; i < t; ++i) {
		cin >> a[i];
	}
	
	for (i = 0; i<t; ++i) {
		if (a[big] <= a[i]) {
			ans = max(ans,i - big-1);
			big = i;
		}
	}
	ans = max(ans, i - big - 1);
	cout << ans;
}

20044 Project Teams

問題は、二人がチームになるとき、一定のバランスを保ち、最大の最高値を見つけることです.
列を作って、最後と前を合わせるだけで、最高の状態になります.

ax<日、bx<がax+bx#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <cstring> #include <cstdio> #include <functional> #include <algorithm> #include <cstdlib> #include <vector> #include <ctime> #include <cmath> #include <stack> #include <string> #define ll long long #define len 1001 using namespace std; int ans, big,i; int main(void) { freopen("input.txt", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 0; cin >> t; t *= 2; vector<int> a(t); for (int i = 0; i < t; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); ans = -1; for (int i = 0; i < t; ++i) { if (ans == -1 || a[t - 1 - i] + a[i] < ans) { ans = a[t - 1 - i] + a[i]; } } cout << ans; }