[CF1020A-C] Codeforces Round #503 (Div.2)

发表于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1020

上分啦

A：n个楼每个楼h层，在每栋楼的$[a,b]$层上都有一个横向的通道，可以从一个楼去任意楼。现在给你两个位置，问最少要走多少步。

对两个位置和通道区间进行讨论，然后抠一下就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
LL n, h, a, b, k;

signed main() {
  // freopen("in", "r", stdin);
  LL ta, fa, tb, fb;
  while(cin>>n>>h>>a>>b>>k) {
    while(k--) {
      cin>>ta>>fa>>tb>>fb;
      LL ret = (LL)abs(ta - tb);
      if(ta == tb) {
        ret += (LL)abs(fa - fb);
      }
      else {
        if(fa > b && fb > b) {
          ret += (fa + fb - 2LL * b);
        }
        else if(fa < a && fb < a) {
          ret += (2LL * a - fa - fb);
        }
        else ret += (LL)abs(fa - fb);
      }
      printf("%lld\n", ret);
    }
  }
  return 0;
}

B：意思就是让你从每个人出发找第一个遍历2次的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
int n, p[maxn];
int vis[maxn];
void dfs(int u) {
  if(vis[u]) {
    printf("%d ", u);
    return;
  }
  vis[u] = 1;
  dfs(p[u]);
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d", &n)) {
    memset(p ,0, sizeof(p));
    int u;
    for(int i = 1; i <= n; i++) {
      scanf("%d", &u);
      p[i] = u;
    }
    for(int i = 1; i <= n; i++) {
      memset(vis, 0, sizeof(vis));
      dfs(i);
    }
    printf("\n");
  }
  return 0;
}

C：n个人要给m个政党投票，每个人都有自己的投票目标以及花钱收买他的代价。现在希望让1号政党的票数超过其他所有政党的票数，问你至少要花多少钱。

考虑贪心地选花费最少的，但是直接这样选相当于确定了收买人数，实际上可以买某一个政党的一些票就可以减少收买人数。于是我们考虑枚举1号政党的目标票数，超过该票数的政党则购买所有最少价格的差票，如果还不足我们的目标票数则从剩下的票里选最便宜的买。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 3030;
int n, m, W;
vector<int> f[maxn];
vector<int> tmp;
int p[maxn], w[maxn];

LL gao(int vote) {
  LL ret = 0;
  tmp.clear();
  int need = vote - W;
  for(int i = 2; i <= m; i++) {
    int id = 0;
    if(f[i].size() >= vote) {
      id = f[i].size() - vote + 1;
    }
    if(id > need) return 1E18;
    need -= id;
    for(int j = 0; j < id; j++) {
      ret += f[i][j];
    }
    for(int j = id; j < f[i].size(); j++) {
      tmp.push_back(f[i][j]);
    }
  }
  sort(tmp.begin(), tmp.end());
  for(int i = 0; i < need; i++) {
    ret += tmp[i];
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&m)) {
    for(int i = 1; i <= n; i++) f[i].clear();
    for(int i = 1; i <= n; i++) {
      scanf("%d%d",&p[i],&w[i]);
      f[p[i]].push_back(w[i]);
    }
    for(int i = 1; i <= m; i++) {
      sort(f[i].begin(), f[i].end());
    }
    LL ret = 1E18;
    W = f[1].size();
    for(int i = W; i <= n; i++) {
      ret = min(ret, gao(i));
    }
    printf("%lld\n", ret);
  }
  return 0;
}