Codeforces Round #823 (Div. 2)

---

前言

D题想不出来 QAQ

---

一、A Planets

• 题目:
  两种操作
  1: 删除一个数字花费1
  2: 删除某个位置上面有的数字花费c,
  问删除所有数字的最小花费是多少
• 思路: 遍历每一个位置,判断一下这个位置使用操作1的花费少还是操作2的花费少,相加即可
• 代码:

#include <bits/stdc++.h>
#define int long long 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,char>
using namespace std;

const int N = 1e5 + 100,M = N * 2,INF = 0x3f3f3f3f;
int a[N];

void solve()
{
     int n,c; cin >> n >> c;
     vector<int> res;
     
     for(int i = 1;i <= n;i ++ )
     {
         int x; cin >> x;
         a[x]++;
         if(a[x] == 1)
         res.pb(x);
     }
     
     int sum = 0;
     for(int i = 0;i < res.size();i ++ )
     {
         if(a[res[i]] > c)
         sum += c;
         else
         sum += a[res[i]];
         
         a[res[i]] = 0;
         
     }
     
     cout << sum << endl;
}

signed main()
{
    
    ios;
    int T;cin >> T; while(T -- ) solve();
    return 0;
}
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

二、B - Meeting on the Line

• 题目: 在x轴上面选择一个位置,x0,其他人到这个位置的时间为 T = ti + abs(X0 - Xi),问你是否能够找到一个点使得,最大的T最小?

• 思路: 可以二分最大值T,然后遍历一遍所有的xi,看看他们是否有共同的区间 ,最后这个区间一定是一个数字,这个数字就是题目求的点,注意二分的时候是double,T不一定是整数 每一个点的区间的左端点是xi - (T - ti),右端点是xi + (T - ti),因为不管枚举的T是几,当前这个点xi 一点要加上去ti,所以一定是要先减去这个ti

• 代码:

#include <bits/stdc++.h>
//#define int long long 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,char>
using namespace std;

const int N = 1e5 + 100,M = N * 2,INF = 0x3f3f3f3f;
int a[N];
double ans;
int n;
struct node
{
    int id,ti;
}e[N];

bool cmp(node x,node y)
{
    return x.id < y.id;
}

bool check(double tim)
{
    double L = -1e9,R = 1e9;
    
    for(int i = 1;i <= n;i ++ )
    {
        double k = tim - e[i].ti;
        
        if(k < 0) return false; // 代表tim < ti,一定不可以,因为不管xi是几最后都要加上ti
        double ll = e[i].id - (tim - e[i].ti);
        double rr = e[i].id + (tim - e[i].ti);
        
        L = max(ll,L);
        R = min(rr,R);
        
        if(R - L < 0) return false; // 代表没有共同区间
    }
    ans = L;
    return true;
}

void solve()
{
      scanf("%d", &n);
     vector<int> res;
     int sum = 0;
     for(int i = 1;i <= n;i ++ ) 
     {
        int x; 
        scanf("%d", &x);
         e[i].id = x;
     }
     for(int i = 1;i <= n;i ++ )
     {
         int x;
         scanf("%d", &x);
         e[i].ti = x;
     }
     sort(e + 1,e + 1 + n,cmp);
     
     double l = e[1].ti,r = 1e9;
     
     while(r - l >= 1e-6)
     {
         double mid = (l + r) / 2;
         if(check(mid)) // 让他更小
         {
             r = mid;
         }
         else
         {
             l = mid;
         }
     }
     
     printf("%.1lf\n",fabs(ans));
}

int main()
{
    
   // ios;
    int T;scanf("%d", &T);; while(T -- ) solve();
    return 0;
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

三、C - Minimum Notation

• 题目: 给你一个字符串s,都是数字,然后让你操作过后使得s在字典序里面最小
  操作: 你可以删除一个数字x,然后在这个数组的任意位置加上去一个min(x + 1,9)

• 思路: 每一次操作都会出现一个x + 1,的数字,所有能不用尽量不用,遍历每一个元素,如果当前元素与栈中的元素比较是非递减的,就无需操作直接进入到栈里面即可,如果是递减,就操作一次,那么这个x + 1,一定在后面的某个位置,但是不清楚在哪个位置,先存起来,最后遍历完以后直接给她排个序就行

• 代码:

#include <bits/stdc++.h>
//#define int long long 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,char>
using namespace std;

const int N = 1e5 + 100,M = N * 2,INF = 0x3f3f3f3f;
stack<char> q;

void solve()
{
     string s; cin >> s;
     vector<char> res;
     
     for(int i = 0;i < s.size();i ++ )
     {
        
             while(q.size())
             {
                 char op = q.top();
                 if(s[i] < op)
                 {
                     q.pop();
                     if(op == '9')
                     res.pb(op);
                     else
                     res.pb((char)op + 1);
                 }
                 else
                 break;
             }
             
            q.push(s[i]);
     }
     
     while(q.size()) //栈中还有的元素别忘记了
     {
         char op = q.top();q.pop();
         res.pb(op);
     }
     
     sort(res.begin(),res.end());
     
     for(auto x:res)
     cout << x;
     cout << endl;
}

int main()
{
    
    ios;
    int T;cin >> T; while(T -- ) solve();
    return 0;
}
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
56
57
58

---

总结

感觉D题想不出来,呜呜