链接

A. Planets (贪心)

贪心，记录每一个轨道上面有多少行星，然后比较个数和c.

参考代码：

#include using i64 = long long;template 
inline void read(T &f) {f = 0; T fu = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }f *= fu;
}int main() {int t;read(t);//t组测试while (t--) {int n, c, ans = 0;//ans初始化为0read(n), read(c);std::vector orbit[101];//背包形式的vector数组,也可以弄成std::map> orbit;std::vector a(n);for (int i = 0; i < n; i++) {read(a[i]);orbit[a[i]].emplace_back(i);//该行星位于轨道A[i]上面//emplace_back() 同 push_back()}for (int i = 1; i <= 100; i++) {ans += std::min(c, (int)(orbit[i].size()));//对于每一个轨道,取最小值累加即可.}printf("%d\n", ans);}return 0;
}

STL::unordered_map： 

#include using i64 = long long;template 
inline void read(T &f) {f = 0; T fu = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }f *= fu;
}int main() {int t;read(t);while (t--) {int n, c, ans = 0;read(n), read(c);std::unordered_map> orbit;std::vector a(n);for (int i = 0; i < n; i++) {read(a[i]);orbit[a[i]].emplace_back(i);}for (auto x : orbit) {ans += std::min((int)(x.second.size()), c);}printf("%d\n", ans);}return 0;
}

B. Meeting on the Line

题意：

有n个人要到一个地方集合，每人要从a[i]出发，出发前要打扮t[i]分钟，走一单位的距离要花费1时间，求最合适的集合的位置,使得集合所需的时间最少。 

方法1：二分时间(具有单调性),对于一个固定的时间,每个人的起始位置为一个区间,所有区间交集就是可行点的集合. 

参考代码：

#include using i64 = long long;
constexpr int MOD = 1e9 + 7, N = 3e5 + 10;template 
inline void read(T &f) {f = 0; T fu = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }f *= fu;
}void solve() {int n;read(n);std::vector x(n), t(n);for (int i = 0; i < n; i++) {read(x[i]);}for (int i = 0; i < n; i++) {read(t[i]);}double left = 0, right = 1e9;double ans = -1;while (right - left > 1e-7) {double l = 0, r = 1e9;double mid = (left + right) / 2;bool success = true;for (int i = 0; i < n && success; i++) {if (mid < t[i]) {success = false;break;}l = std::max(l, x[i] + t[i] - mid);r = std::min(r, x[i] - t[i] + mid);if (r < l) {success = false;}}if (success) {right = mid;ans = l;}   else {left = mid;}}printf("%.7lf\n", ans);//注意精度问题
}int main() {int t;read(t);while (t--) {solve();}return 0;
}

参考代码：

#include using i64 = long long;
constexpr int MOD = 1e9 + 7, N = 3e5 + 10;template 
inline void read(T &f) {f = 0; T fu = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }f *= fu;
}void solve() {int n;read(n);std::vector x(n), t(n);for (int i = 0; i < n; i++) {read(x[i]);}for (int i = 0; i < n; i++) {read(t[i]);}double a = 0, b = 1e9;for (int i = 0; i < n; i++) {a = std::max(a, 0.0 + x[i] + t[i]);b = std::min(b, 0.0 + x[i] - t[i]);}printf("%.7lf\n", (a + b) / 2);//注意精度问题
}
int main() {int t;read(t);while (t--) {solve();}return 0;
}

C. Minimum Notation

题意：

给定一个由数字构成的字符串,每次操作可以选择一个位置,删除对应位置的数x,然后将min(x + 1, 9)插入到任意一个位置中.问可以得到的最小字典序的字符串是什么.

思路：

贪心. 我们应当优先选取小的数字.先记录每个数字出现的位置，然后从小到大,开始贪心选取每个数字,并记录当前的右端点.如果当前数字的位置在右端点前,说明它需要被删除,再插入,删除后插入的位置是任意的,我们可以留到最后插入比小的位置的后面最优.

参考代码：

void solve() {std::string s;std::cin >> s;std::vector> pos(10);for (int i = 0; i < s.size(); i++) {pos[s[i] - '0'].emplace_back(i);}int cur = -1;std::vector cnt(10);for (int i = 0; i < 10; i++) {for (int p : pos[i]) {if (p > cur) {cur = p;cnt[i]++;} else {cnt[std::min(i + 1, 9)]++;}}}for (int i = 0; i < 10; i++) {while (cnt[i]--) {printf("%d", i);}}printf("\n");
}

倒序处理起来比较方便,每遇到一个更小的数,说明大的数全部都要增加.

问题其实可以这么考虑,对于每个数i,如果后面没有比i大的,那么i就可以取,按这种思路逆序是很自然的. 倒序,然后记录当前最小值

这种问题其实出现过很多次,只不过是作为难题中的一小步.

// from jiangly
void solve() {std::string s;std::cin >> s;const int n = s.length();char x = '9';std::array cnt{};for (int i = n - 1; i >= 0; i--) {if (s[i] <= x) {cnt[s[i] - '0']++;x = s[i];} else {cnt[std::min(9, s[i] - '0' + 1)]++;}}for (int i = 0; i < 10; i++) {std::cout << std::string(cnt[i], '0' + i);}std::cout << "\n";
}