贪心算法集

去重数组#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; xn%3; if(x0) printf(%d\n,n/3); else printf(%d\n,n/31); 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[i1]); 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 count0; for(int i0;in;i) { int a; scanf(%d,a); if(a%20) count; } if(countn) 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*(n1)/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 i0;in;i) { scanf(%d,a[i]); } for(int in;i2*n;i) { scanf(%d,a[i]); } qsort(a,2*n,sizeof(int),cmp); int ansa[n-1]-a[0]; for(int i1;in;i) { int diffa[in-1]-a[i]; if(diffans) ansdiff; } 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[i1] 1 - diff[i1]; // 翻转下一个 } } 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[a1] exist[a2]) { res; } } printf(%d\n, res); return 0; }