您希望在處理學生成績時收集資訊。學校學生的默認串列編號為“1、2、3、4...”，程式必須處理以下指令：
- 注冊 ( c )：注冊串列中的下一個學生獲得了c級。
- COUNT ( c, i, j )：統計[ i, j ]（含）之間有多少個成績為c的學生。
輸入：
一個整數N后跟要處理的N條指令。您可以假設0 <= N <= 100000，成績在 0 到 100 之間，并且所有串列編號范圍將指已注冊的學生。OUTPUT：
每個COUNT指令的對應值。例子：
輸入：
7 REGISTER 8 REGISTER 7 REGISTER 8 COUNT 8 1 2 COUNT 8 1 3 REGISTER 7 COUNT 7 1 2輸出：
1 2 1
你可以想象，這是一個互聯網問題（這個），我想出了這個解決方案：
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::vector<short> A;
int N;
std::cin >> N;
while (N--) {
std::string W;
std::cin >> W;
if (W == "REGISTER") {
short C;
std::cin >> C;
A.push_back(C);
} else {
int I, J;
short C;
std::cin >> C >> I >> J;
std::cout << std::count(A.begin() I - 1, A.begin() J, C)
<< "\n";
}
}
return 0;
}
顯然我的代碼很慢。有人可以幫我找到更有效的解決方案嗎？想了很久，還是沒有辦法。
uj5u.com熱心網友回復：
決定為您實施3個解決方案。第SolveSimple()一個和你的一樣，我做它是為了測驗另外兩個的正確性。其次SolveBinSearch()是基于二分搜索方法。三SolveDynProg()是基于動態規劃的方法。
簡單的解決方案（和你的一樣）10x比其他兩個慢幾倍。二分搜索2x比動態編程變體更快。二進制搜索變體也比 dyn prog 更節省記憶體，但對于100 K指令的情況，這種記憶體經濟不是大問題。
我的代碼中的測驗是隨機生成的。你可以調整的測驗指令數num_instructions和max_grade，也標志verbose控制是否像每一個方法的答案輸出額外的除錯資訊。在代碼之后你會發現時間。
三種方法中的每一種都接受輸入和輸出流，您可以只傳遞標準輸入和輸出，例如SolveBinSearch(std::cin, std::cout);，在將解決方案發送到在線比賽評判系統的情況下。
如果選擇那么SolveBinSearch()是最快和記憶體經濟的解決方案。
在線試試吧！
#include <random>
#include <sstream>
#include <string>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <array>
#include <chrono>
using std::size_t;
using u8 = uint8_t;
using u32 = uint32_t;
void SolveSimple(std::istream & inp, std::ostream & out) {
std::vector<u8> grades;
while (inp) {
std::string cmd;
inp >> cmd;
if (cmd == "REGISTER") {
size_t grade = 0;
inp >> grade;
grades.push_back(grade);
} else if (cmd == "COUNT") {
size_t grade = 0, i = 0, j = 0;
inp >> grade >> i >> j;
out << std::count(grades.begin() (i - 1),
grades.begin() j, grade) << std::endl;
} else
break;
}
}
void SolveBinSearch(std::istream & inp, std::ostream & out) {
// https://en.wikipedia.org/wiki/Binary_search_algorithm
std::vector<std::vector<u32>> cnts(101);
size_t cnt = 0;
while (inp) {
std::string cmd;
inp >> cmd;
if (cmd == "REGISTER") {
size_t grade = 0;
inp >> grade;
cnts[grade].push_back(cnt);
cnt;
} else if (cmd == "COUNT") {
size_t grade = 0, i = 0, j = 0;
inp >> grade >> i >> j;
auto begin = std::lower_bound(
cnts[grade].begin(), cnts[grade].end(), i - 1);
auto end = std::upper_bound(
cnts[grade].begin(), cnts[grade].end(), j - 1);
out << (end - begin) << std::endl;
} else
break;
}
}
void SolveDynProg(std::istream & inp, std::ostream & out) {
// https://en.wikipedia.org/wiki/Dynamic_programming
std::vector<std::array<u32, 101>> cnts(1);
while (inp) {
std::string cmd;
inp >> cmd;
if (cmd == "REGISTER") {
size_t grade = 0;
inp >> grade;
cnts.push_back(cnts.back());
cnts.back()[grade];
} else if (cmd == "COUNT") {
size_t grade = 0, i = 0, j = 0;
inp >> grade >> i >> j;
out << cnts[j][grade] - cnts[i - 1][grade] << std::endl;
} else
break;
}
}
void Test() {
bool constexpr verbose = 0;
size_t constexpr num_instructions = 100000, max_grade = 100;
auto TimeCur = []{
return std::chrono::high_resolution_clock::now();
};
auto const gtb = TimeCur();
auto Time = [&]{
return std::chrono::duration_cast<std::chrono::microseconds>(
TimeCur() - gtb).count() / 1000000.0;
};
std::mt19937_64 rng{123};
std::stringstream inp;
size_t cnt = 0;
for (size_t i = 0; i < num_instructions; i) {
if ((rng() & 1) || (cnt == 0)) {
cnt;
inp << "REGISTER " << rng() % (max_grade 1) << std::endl;
} else {
size_t a = rng() % cnt 1, b = rng() % cnt 1;
if (a > b)
std::swap(a, b);
inp << "COUNT " << rng() % (max_grade 1) << " "
<< a << " " << b << std::endl;
}
}
auto inp_str = inp.str();
if (verbose) {
std::cout << "Input: " << std::endl
<< inp.str() << std::endl;
}
std::cout << std::fixed << std::boolalpha;
double tb = 0;
std::stringstream out_simple, out_binsearch, out_dynprog;
tb = Time(); inp.clear(); inp.str(inp_str);
SolveSimple(inp, out_simple);
std::cout << "Simple time " << (Time() - tb) << std::endl;
tb = Time(); inp.clear(); inp.str(inp_str);
SolveBinSearch(inp, out_binsearch);
std::cout << "BinSearch time " << (Time() - tb) << std::endl;
tb = Time(); inp.clear(); inp.str(inp_str);
SolveDynProg(inp, out_dynprog);
std::cout << "DynProg time " << (Time() - tb) << std::endl;
if (verbose) {
std::cout << "Simple: " << std::endl
<< out_simple.str() << std::endl;
std::cout << "BinSearch: " << std::endl
<< out_binsearch.str() << std::endl;
std::cout << "DynProg: " << std::endl
<< out_dynprog.str() << std::endl;
}
std::cout << "Simple == BinSearch: "
<< (out_simple.str() == out_binsearch.str()) << std::endl;
std::cout << "Simple == DynProg: "
<< (out_simple.str() == out_dynprog.str()) << std::endl;
std::cout << "BinSearch == DynProg: "
<< (out_binsearch.str() == out_dynprog.str()) << std::endl;
}
int main() {
Test();
}
輸出：
Simple time 0.184678
BinSearch time 0.020600
DynProg time 0.048994
Simple == BinSearch: true
Simple == DynProg: true
BinSearch == DynProg: true
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387595.html
上一篇：查找在其他陣列中重復的陣列
下一篇：通過字串值從無序映射中獲取列舉鍵