贪心算法集

去重数组

#include <stdio.h> int main() { int n; scanf("%d", &n); int a[55]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int seen[1005] = {0}; // 标记是否已经选择保留（从右往左第一次遇到） int keep[55], k = 0; // 保留的元素（实际我们只需要和） // 从右往左扫描 for (int i = n - 1; i >= 0; i--) { if (!seen[a[i]]) { seen[a[i]] = 1; keep[k++] = a[i]; } } // 保留的元素是 keep 里的，但注意我们是从右往左加入的，顺序不重要，我们要求和 int sum = 0; for (int i = 0; i < k; i++) { sum += keep[i]; } int remove_count = n - k; printf("%d\n", remove_count); printf("%d\n", sum); return 0; }

谈判

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { int n; scanf("%d", &n); int t[n]; for (int i = 0; i < n; i++) { scanf("%d", &t[i]); } long long cost = 0; int size = n; while (size > 1) { // 排序找到最小的两个 qsort(t, size, sizeof(int), cmp); // 合并最小的两个 int sum = t[0] + t[1]; cost += sum; // 用 sum 替换 t[0]，移除 t[1] t[0] = sum; for (int i = 1; i < size - 1; i++) { t[i] = t[i + 1]; } size--; } printf("%lld\n", cost); return 0; }

最小步数

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int n; scanf("%d",&n); int x; x=n%3; if(x==0) printf("%d\n",n/3); else printf("%d\n",n/3+1); return 0; }

最小化战斗力差距

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { return *(long long*)a - *(long long*)b; } int main() { int n; scanf("%d", &n); long long w[n]; for (int i = 0; i < n; i++) { scanf("%lld", &w[i]); } // 排序 qsort(w, n, sizeof(long long), cmp); long long min_gap = 1LL << 60; // 很大的数 for (int i = 0; i < n - 1; i++) { long long diff = llabs(w[i] - w[i+1]); if (diff < min_gap) { min_gap = diff; } } printf("%lld\n", min_gap); return 0; }

平衡魔方

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int count=0; for(int i=0;i<n;i++) { int a; scanf("%d",&a); if(a%2==0) count++; } if(count==n) printf("0\n"); else printf("%d\n",count); } return 0; }

字符串的切分

#include <stdio.h> #include <string.h> int main() { int n; scanf("%d", &n); char t[100005]; scanf("%s", t); int count[26] = {0}; for (int i = 0; i < n; i++) { count[t[i] - 'a']++; } int ans = 0; for (int i = 0; i < 26; i++) { if (count[i] > ans) { ans = count[i]; } } printf("%d\n", ans); return 0; }

最多表示数

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { long long n; scanf("%lld",&n); printf("%lld",n*(n+1)/2); return 0; }

宝石塔的亮度差异

#include <stdio.h> #include <stdlib.h> int cmp(const void* a,const void* b) { return *(int*)a-*(int*)b; } int main(int argc, char *argv[]) { int n; scanf("%d",&n); int a[2*n]; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } for(int i=n;i<2*n;i++) { scanf("%d",&a[i]); } qsort(a,2*n,sizeof(int),cmp); int ans=a[n-1]-a[0]; for(int i=1;i<=n;i++) { int diff=a[i+n-1]-a[i]; if(diff<ans) ans=diff; } printf("%d\n",ans); return 0; }

纪念品分组

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { int w, n; scanf("%d %d", &w, &n); int *prices = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { scanf("%d", &prices[i]); } // 排序 qsort(prices, n, sizeof(int), cmp); int left = 0, right = n - 1; int groups = 0; while (left <= right) { if (left == right) { groups++; break; } if (prices[left] + prices[right] <= w) { groups++; left++; right--; } else { groups++; right--; } } printf("%d\n", groups); free(prices); return 0; }

翻硬币

#include <stdio.h> #include <string.h> int main() { char S[1005], T[1005]; scanf("%s %s", S, T); int n = strlen(S); int diff[1005]; for (int i = 0; i < n; i++) { diff[i] = (S[i] != T[i]); } int ans = 0; for (int i = 0; i < n; i++) { if (diff[i] == 1) { ans++; diff[i] = 0; diff[i+1] = 1 - diff[i+1]; // 翻转下一个 } } printf("%d\n", ans); return 0; }

找零硬币数

#include <stdio.h> int main() { int M; scanf("%d", &M); int coins[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1}; int n = sizeof(coins) / sizeof(coins[0]); int count = 0; for (int i = 0; i < n; i++) { if (M >= coins[i]) { count += M / coins[i]; M %= coins[i]; } } printf("%d\n", count); return 0; }

一键3连

#include <stdio.h> int main() { int n; scanf("%d", &n); int A[100005]; int exist[100005] = {0}; int max_val = 0, min_val = 100005; for (int i = 0; i < n; i++) { scanf("%d", &A[i]); exist[A[i]] = 1; if (A[i] > max_val) max_val = A[i]; if (A[i] < min_val) min_val = A[i]; } int res = 0; // 只检查到 max_val - 2 即可 for (int a = min_val; a <= max_val - 2; a++) { if (exist[a] && exist[a+1] && exist[a+2]) { res++; } } printf("%d\n", res); return 0; }