CF R767 C. Meximum Array

Problem.

https://codeforces.com/contest/1629/problem/C

Idea.

Find mex for all suffix a[i:n-1]
Split the array greedily.

Source.

 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           int n; cin >> n;  
           vector<int> a(n);  
           REP(i, n) cin >> a[i];  
           // find all suffix mex a[i:n-1]  
           vector<int> mex(n);  
           vector<int> cnt(n + 10, 0);  
           int now = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                cnt[a[i]]++;  
                if (a[i] == now) {  
                     while (cnt[now]) now++;  
                }  
                mex[i] = now;  
           }  
           // split the array  
           vector<int> ret;  
           int cur = 0;  
           while (cur < n) {  
                ret.push_back(mex[cur]);  
                int i = cur;  
                set<int> st;  
                while (i < n) {  
                     if (a[i] < mex[cur]) st.insert(a[i]);  
                     if (st.size() == mex[cur]) break;  
                     i++;  
                }  
                cur = i + 1;  
           }  
           cout << ret.size() << endl;  
           for (int x : ret) cout << x << " "; cout << endl;  
      }  
 }  

POJ.3045 Cow Acrobats

1.Problem
http://poj.org/problem?id=3045

2.Idea
Greedy approach is accepted. Order the cows in (W_i + S_i).

3.Source

 int N;  
 struct Test {  
      ll w, s;  
      bool operator < (const Test &a)const {  
           return w + s < a.w + a.s;  
      }  
 } Tests[50004];  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d%d", &Tests[i].w, &Tests[i].s);  
      sort(Tests, Tests + N);  
      ll ans = -123456789;  
      ll cum = 0;  
      for (int i = 0; i < N; i++) {  
           ll tmp = cum - Tests[i].s;  
           cum += Tests[i].w;  
           ans = max(ans, tmp);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3614 Sunscreen

1.Problem
http://poj.org/problem?id=3614

2.Idea
Greedy method works. Process from the cow that has the min of maxSPF.

3.Source

 int c, l;  
 int Lot[1003];  
 struct Cow {  
      int l, r;  
      bool operator < (const Cow &a)const {  
           return r < a.r;  
      }  
 } Cows[2503];  
 int main()  
 {  
      cin >> c >> l;  
      for (int i = 0; i < c; i++) {  
           cin >> Cows[i].l >> Cows[i].r;  
      }  
      sort(Cows, Cows + c);  
      for (int i = 0; i < l; i++) {  
           int x, y;  
           cin >> x >> y;  
           Lot[x] += y;  
      }  
      int ans = 0;  
      for (int i = 0; i < c; i++) {  
           for (int j = Cows[i].l; j <= Cows[i].r; j++) {  
                if (Lot[j] > 0) {  
                     ans++;  
                     Lot[j]--;  
                     break;  
                }  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1862 Stripies

1.Problem
http://poj.org/problem?id=1862

2.Idea
Pick the biggest 2 value, and process them, return to queue.

3.Source

 int n;  
 double a[111];  
 priority_queue<double> q;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
           q.push(a[i]);  
      }  
      for (int i = n - 1; i > 0; i--) {  
           double A = q.top(); q.pop();  
           double B = q.top(); q.pop();  
           q.push(2 * sqrt(A * B));  
      }  
      cout << fixed << std::setprecision(3) << q.top() << endl;  
      return 0;  
 }  

POJ.2393 Yogurt factory

1. Problem
http://poj.org/problem?id=2393

2. Idea
Each week, comparing current week cost and last week cost + storage cost, choose the small one.

3. Source

 int n;  
 ll s;  
 ll total = 0;  
 ll cur = 0;  
 int main()  
 {  
      cin >> n >> s;  
      for (int i = 0; i < n; i++) {  
           ll c, y;  
           cin >> c >> y;  
           if (i == 0) {  
                cur = c;  
                total = cur * y;  
                continue;  
           }  
           cur = min(cur + s, c);  
           total += (cur * y);  
      }  
      cout << total << endl;  
      return 0;  
 }  

POJ. 3262 Protecting the Flowers

1.Problem
http://poj.org/problem?id=3262

2.Idea
Sort the cows by damage order, the process in that order all line.

3.Source

 struct Point {  
      ll t, d;  
      bool operator < (const Point &a)const {  
                return t * a.d < d * a.t;  
      }  
 } Points[100005];  
 int n;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> Points[i].t >> Points[i].d;  
      }  
      sort(Points, Points + n);  
      ll ans = 0;  
      int T = 0;  
      for (int i = 0; i < n; i++) {  
           ans += T * Points[i].d;  
           T += (2 * Points[i].t);  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3040 Allowance

1.Problem
http://poj.org/problem?id=3040

2.Idea
Need to do 2 run greedy calculation. Build a valid coin combination for a allowance as much as close to value c with the following approach:
first run: Start filling from biggest valued coin, and taking as many as possible
second run: If there is still remainder, this time start use smallest valued coins.

3.Source:

 struct Bill {  
      int v, b;  
      bool operator < (const Bill &a)const {  
           return v > a.v;  
      }  
 } Bills[22];  
 int use[22];  
 int n, c;  
 int k = 0;  
 int ans = 0;  
 int main()  
 {  
      cin >> n >> c;  
      for (int i = 0; i < n; i++) {  
           int v, b;  
           cin >> v >> b;  
           Bills[i].v = v;  
           Bills[i].b = b;  
      }  
      // sort by decreasing order of coin value  
      sort(Bills, Bills + n);  
      while (1) {  
           int rest = c;  
           memset(use, 0, sizeof use);  
           // use coins from biggest size:like 50, 10, 5, 1  
           for (int i = 0; i < n; i++) {  
                int tmp = min(Bills[i].b, rest / Bills[i].v);  
                use[i] = tmp;  
                rest -= tmp * Bills[i].v;  
           }  
           // if still need, this time use coin from smallest value: like 1, 5, 10, 50  
           int i = n - 1;  
           while (rest > 0 && i >= 0) {  
                int tmp = min((Bills[i].b - use[i]), (int)ceil((double)rest / (double)Bills[i].v));  
                use[i] += tmp;  
                rest -= tmp * Bills[i].v;  
                i--;  
           }  
           // if can't fill a full allowance, to leave  
           if (rest > 0) break;  
           // get the max possible allowance number for the current combination  
           int MinUse = INF;  
           for (int i = 0; i < n; i++) {  
                if (use[i]) {  
                     MinUse = min(MinUse, Bills[i].b / use[i]);  
                }  
           }  
           // if can't get any number then leave  
           if (MinUse == INF) break;  
           // subtruct used coins from respective vars  
           for (int i = 0; i < n; i++) {  
                Bills[i].b -= (use[i] * MinUse);  
           }  
           ans += MinUse;            
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1328 Radar Installation

1. Problem
http://poj.org/problem?id=1328

2.Idea
Using greedy method, but not just based on X axis order of icelands, instead, using X axis projection segment.

X axis projection segment

3. Source:

 struct Point {  
      double x, y;  
      double s, e; //projection segment to X axis  
      bool operator < (const Point &a)const {  
           return e < a.e;  
      }  
 } Points[1003];  
 int n, d, flag;  
 int solve()  
 {  
      int ans = 1;  
      sort(Points, Points + n);  
      double r = Points[0].e;  
      for (int i = 1; i < n; i++) {  
           if (r < Points[i].s) {  
                r = Points[i].e;  
                ans++;  
           }  
      }  
      return ans;  
 }  
 int main()  
 {  
      int t = 1;  
      while (1) {  
           scanf("%d%d", &n, &d);  
           if (n + d == 0) break;  
           flag = 0;  
           for (int i = 0; i < n; i++) {  
                int x, y;  
                scanf("%d%d", &x, &y);  
                if (y > d) flag = 1;  
                Points[i].x = (double)x;  
                Points[i].y = (double)y;  
                Points[i].s = x - sqrt((double)d * d - (double)y * y);  
                Points[i].e = x + sqrt((double)d * d - (double)y * y);  
           }  
           printf("Case %d: ", t);  
           if (flag) puts("-1");  
           else printf("%d\n", solve());  
           t++;  
      }  
      return 0;  
 }  

POJ.3190 Stall Reservations

1.Problem:
http://poj.org/problem?id=3190

2.Idea:
Pick items from earlier starting order, and use priority_queue as data structure to simulate stall stations.

3.Source

 struct Interval {  
      int start, end, num;  
      bool operator < (const Interval &a)const {  
           return end>a.end;  
      }  
 } Cows[50004];  
 bool comp(Interval a, Interval b)  
 {  
      if (a.start == b.start) {  
           return a.end < b.end;  
      }  
      else return a.start < b.start;  
 }  
 int n;  
 int ans[50004];  
 int cur = 1;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d%d", &Cows[i].start, &Cows[i].end);  
           Cows[i].num = i;  
      }  
      sort(Cows, Cows + n, comp);  
      priority_queue<Interval> q;  
      q.push(Cows[0]);  
      ans[Cows[0].num] = cur;  
      for (int i = 1; i < n; i++) {  
           if (q.top().end < Cows[i].start) {  
                int tmp = ans[q.top().num]; q.pop();  
                ans[Cows[i].num] = tmp;  
                q.push(Cows[i]);  
           }  
           else {  
                cur++;  
                ans[Cows[i].num] = cur;  
                q.push(Cows[i]);  
           }  
      }  
      cout << cur << endl;  
      for (int i = 0; i < n; i++) {  
           printf("%d\n", ans[i]);  
      }  
      return 0;  
 }  

POJ.1017 Packets

Problem:
http://poj.org/problem?id=1017

Idea:
Start packing from bigger sized boxes.

Source:

 int c[6];  
 int x, y;  
 void solve()  
 {  
      int ans = 0;  
      //6*6  
      ans += c[5];  
      //5*5  
      ans += c[4];  
      c[0] = max(0, c[0] - 11 * c[4]);  
      //4*4  
      ans += c[3];  
      x = c[1];  
      c[1] = max(0, c[1] - 5 * c[3]);  
      if (c[1] == 0 && c[3]) {  
           c[0] = max(0, c[0] - (c[3]*20 - x * 4));  
      }  
      //3*3  
      ans += (c[2] / 4);  
      if (c[2] % 4 == 3) {  
           ans++;  
           if (c[1]) {  
                c[1]--;  
                c[0] = max(0, c[0] - 5);  
           }  
           else {  
                c[0] = max(0, c[0] - 9);  
           }  
      }  
      else if (c[2] % 4 == 2) {  
           ans++;  
           if (c[1] >= 3) {  
                c[1]-=3;  
                c[0] = max(0, c[0] - 6);  
           }  
           else {  
                x = c[1];  
                c[1] = 0;  
                c[0] = max(0, c[0] - (18 - x * 4));  
           }  
      }  
      else if (c[2] % 4 == 1) {  
           ans++;  
           if (c[1] >= 5) {  
                c[1] -= 5;  
                c[0] = max(0, c[0] - 7);  
           }  
           else {  
                x = c[1];  
                c[1] = 0;  
                c[0] = max(0, c[0] - (18 - x * 4));  
           }  
      }  
      //2*2  
      ans += (c[1] / 9);  
      if (c[1] % 9) {  
           ans++;  
           c[0] = max(0, c[0] - (36 - 4 * (c[1]%9)));  
      }  
      //1*1  
      if (c[0] % 36 == 0) {  
           ans += (c[0] / 36);  
      }  
      else {  
           ans += (1 + c[0] / 36);  
      }  
      cout << ans << endl;  
 }  
 int main()  
 {  
      while (1) {  
           int sum = 0;  
           for (int i = 0; i < 6; i++) {  
                cin >> c[i];  
                sum += c[i];  
           }  
           if (sum == 0) break;  
           solve();  
      }  
      return 0;  
 }  

POJ.3253 Fence Repair

Problem:
http://poj.org/problem?id=3253

Idea:
Always pick smallest 2.

Source:

 int n;  
 priority_queue<int, vector<int>, greater<int>> q;  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           int t;  
           cin >> t;  
           q.push(t);  
      }  
      ll ans = 0;  
      for (int i = 1; i < n; i++) {  
           int t1 = q.top(); q.pop();  
           int t2 = q.top(); q.pop();  
           q.push(t1 + t2);  
           ans += (t1 + t2);  
      }  
      cout << ans << endl;  
      return 0;  
 }