题意:卖肉问题,当天的价格便宜可以将以后的肉买了,问最少花费多少钱
分析:差点就做不出来了,维护一个动态的前缀最小值,如果当前的价格便宜则更新最小值,当天的肉用最小值买。
#include <cstdio> const int N = 1e5 + 10; int a[N], p[N]; int main(void) { int n; scanf ("%d", &n); int ans = 0, mn = 111; for (int i=1; i<=n; ++i) { scanf ("%d%d", &a[i], &p[i]); if (p[i] < mn) mn = p[i]; ans += a[i] * mn; } printf ("%d ", ans); return 0; }
水+约数枚举 B - Duff in Love
暴力枚举一下就可以了
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; void divisor(ll n, vector<ll> &ret) { ret.clear (); for (ll i=1; i*i<=n; ++i) { if (n % i == 0) { ret.push_back (i); if (n / i != i) ret.push_back (n / i); } } ret.push_back (n); sort (ret.begin (), ret.end ()); } int main(void) { ll n; scanf ("%I64d", &n); if (n == 1) { puts ("1"); return 0; } vector<ll> div; divisor (n, div); for (int i=div.size ()-1; i>=0; --i) { ll x = div[i]; if (sqrt (x) * sqrt (x) == x) continue; bool flag = true; for (ll j=2; j*j<=x; ++j) { ll y = j * j; if (x % y == 0) { flag = false; break; } } if (flag) { printf ("%I64d ", x); return 0; } } return 0; }
题意:1024游戏
分析:考虑两个两个进位,如果是奇数的多一个步骤,在最后统计要累加的步骤数
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int cnt[N]; int w[N]; int main(void) { int n; scanf ("%d", &n); int mx = -1, mn = INF; for (int i=1; i<=n; ++i) { scanf ("%d", &w[i]); if (mx < w[i]) mx = w[i]; if (mn > w[i]) mn = w[i]; cnt[w[i]]++; } int ans = 0, pre = 0; for (int i=mn; i<=mx; ++i) { if (i == mn) { pre = cnt[i] / 2; if (cnt[i] & 1) ans++; } else { cnt[i] += pre; pre = cnt[i] / 2; if (cnt[i] & 1) ans++; } } while (pre) { if (pre & 1) ans++; pre >>= 1; } printf ("%d ", ans); return 0; }