Codeforces Round 965 (Div. 2) 8.10

8.10 Div 2

Codeforces Round 965 (Div. 2)

A. Find K Distinct Points with Fixed Center

输入x,y,k。输出k对xi ,yi。所有xi,yi平均数分别为x,y

思路

代码很早就敲完了，不确定又去看了看题，这一看，误以为自己写错了，后来晃过神，晚提交了得10min

当k为奇数，就是输出本身。

为偶数，每次输出两个，x+a,x-a,

代码

  int x,y,k;
    cin>>x>>y>>k;
    int a=0;
    for(;k>0;k--)
    {
        if(k&1)
        cout<<x<<" "<<y<<'\n';
        else{
            a++;
            cout<<x-a<<" "<<y-a<<'\n';
            cout<<x+a<<" "<<y+a<<'\n';
            k--;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

B. Minimize Equal Sum Subarrays

给定一个包含（1-n)的序列，输出一个和他区间和相同最小的序列

思路

这题代码敲得也很快，读完题就开敲。不过发现好像没完全理解题，又去读题，读了半晌，就坚定的交上代码了。又晚了几分钟，还好一次过了。

原序列每个加一，n变成1。

代码

void solve()
{
    int n;
    cin>>n;
    fir(i,1,n)
    cin>>a[i];
    fir(i,1,n)
    cout<<a[i]%n+1<<" ";
    cout<<'\n';
    
}
1
2
3
4
5
6
7
8
9
10
11

C. Perform Operations to Maximize Score

k次操作，b数组为1的下标，可以在a数组相应位置进行操作+=1，答案是a数组中一个数+去掉该数的数组中mid。

思路

这个题真该反思。

不求赛时A，但至少把代码敲好样例过了，毕竟有+1/2的细节，如果思路不清晰，没考虑到，就得一直改。

今天看题解，明明昨天思路非常正确，但迟迟不开敲，也只是在最后敲了一个框架。可能是最近写题常看题解，没题解支撑，就不相信自己了，同时高看了C题，轻视了自己的能力。

步入正题

弄几个数组模拟几遍能发现，最终答案一定是（max+mid）,可以比较一下，不会比这个选择更大了。（当然结论很简单，能马上得出要么思路很清晰，要么没考虑清楚的大胆猜。还是需要多想几种可能进行比较）。

所以，我们就考虑制造最大max或者mid

递增排序

• 如果选择前者，可以发现肯定是将k累加到一个数上面，方可

  所以写个循环，将可以操作的数字 a[i]+=k, ans=mid+a[i],

  这里有一个易错点，就是mid到底是谁

  我也是在这里卡了很久，定位总是不准确，有偏差。

  在下面代码中，是从0到n-1存放的，如果去掉一个数中位数下标是 n/2-1,

  而我们要去掉的就是a [ i ]+k

  所以，

  当数字位于它前面（包括中位数），去掉后中位数下标应为n/2

  当数字位于其后，去掉不影响中位数下标，仍为n/2-1

• 选择后者，利用二分找到最大mid,中位数是去掉max后的！！！！

check函数，用 C 计算>=mid的个数，

<mid,且可操作的数字，进行++，达到mid。因为贪心，所以我们从后往前遍历，因为后面大，令k减小的少，可以令更多数字>mid

计算可得大于等于mid的数量为n-n/2（去掉max后！！！），这个地方没考虑全，又卡了。

c>=n-n/2，满足，接着搜素更大mid,进行判断

vector要清空！！！

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<long long,long long> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int n,k;
vector < PII >  a;
bool check(int mid)
{
    int c=0,kk=k;
    for(int i=n-2;i>=0;i--)
    {
        if(a[i].fi>=mid)
        c++;
        else
        {
            if(a[i].se)
            if(mid-a[i].fi<=kk)
            {
                kk=kk-(mid-a[i].first);
                c++;
            }
        }
    }
    if(c>=(n-n/2))//  >=中位数个数
    return 1;
    else return 0;
}
void solve()
{
    a.clear();
    int ans=0;
    cin>>n>>k;
    a.resize(n);
    for(auto &x:a)
    cin>>x.first;
    for(auto &x:a)
    cin>>x.second;
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++)//累加ma
    {
        if(a[i].se==1)
        {
            if(i<=n/2-1 )//去掉一个数中位数下标
            ans=max(a[i].fi+k+a[n/2].fi,ans);//去掉中位数前面的数，中位数后移
            else
            ans=max(a[i].fi+k+a[n/2-1].fi,ans);
        }
    }
    //二分，查找max中位数
    int l=0,r=1e10;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid))
        l=mid;
        else
        r=mid-1;
    }
   
    ans=max(ans,l+a[n-1].first);
    cout<<ans<<'\n'; 
}
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
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

总结

看题得认真，不能迷糊，不然太费时间。

不要自暴自弃，比赛没结束就要用心打，没有哪一题是绝对A不出来的，相信自己的判断