简单算法题
題目一：設(shè)原始數(shù)組為a[]，初始值均為0，我們對數(shù)列a[]進(jìn)行兩種操作：
? ? ? ?（1）對某些數(shù)加1 ? ? （2）對所有的數(shù)乘2
? ? ? ?問至少經(jīng)過多少次操作達(dá)到給定的序列。
?
分析：先對給定的數(shù)組a[]中的奇數(shù)減1，然后對所有的數(shù)除以2，然后反復(fù)進(jìn)行此操作，直到所有的數(shù)為0.
題目二：?http://acm.hdu.edu.cn/showproblem.php?pid=2037
?
分析：先按節(jié)目的結(jié)束時間排序，越早結(jié)束的節(jié)目當(dāng)然要先看，按照這樣的方法處理。
題目三：http://acm.hust.edu.cn/problem.php?id=1618
?
題意：把1~n*n之間的數(shù)填入n*n的矩陣，使得所有兩兩相鄰元素和的最大值最小，求這個最小值。例如n = 2時
1 4
3 2
這種方式形成的最小值為6，其余的填法形成的都比這個值大。
?
分析：這個最小值為：n^2 + n/2 + 1，證明無。
題目四：http://codeforces.com/contest/346/problem/C
題意：給兩個數(shù)字a和b，a>=b，再給一個數(shù)組x[]，現(xiàn)在我們要把a變成b，只能進(jìn)行兩種操作：
? ? ? (1)把a自減1 ? ? ? (2)把a減去a%x[i]
? ? ?現(xiàn)在求最小的步數(shù)把a變?yōu)閎。
分析：本題是很明顯的貪心算法。當(dāng)然在開始之前我們首先要對數(shù)組x[]去重，當(dāng)然這個用sort排一下序，然后用STL的unique，然后就是每次找a%x[i]的最大值，然后還要保證每次a減了之后要大于等于b。
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 100005;int x[N];int main() {int n,a,b;while(scanf("%d",&n)!=EOF){for(int i=0; i<n; i++)scanf("%d",&x[i]);scanf("%d%d",&a,&b);sort(x,x+n);n = unique(x,x+n)-x;int ans = 0;while(a > b){int maxval = 1;for(int i=0; i<n; i++){if(a - a%x[i] >= b)maxval = max(maxval,a%x[i]);}a -= maxval;while(n && a-a%x[n-1] < b) n--;ans++;}printf("%d\n",ans);}return 0; }
總結(jié)
