Znzryb's Blog

ABC-375-D - ABA

Posted on 2024-10-13 Edited on 2026-04-06

题目大意

给定一个字符串 $S$ ，求有多少个三元组 $(i, j, k)$ 满足 $1 \le i < j < k \le |S|$ 且 $S_i = S_k$ 。

AC代码与思路

可以想办法简化这个的计算(用前缀和)

比较具象化的就是这个

然后就AC了，记得开long long

AC https://atcoder.jp/contests/abc375/submissions/58758528

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans=0;
long long sum[30],cnt[30];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        int idx=s[i]-'A';
        ans+=(i*cnt[idx]-sum[idx]-cnt[idx]);
        sum[idx]+=i;
        cnt[idx]++;
    }
    cout<<ans<<endl;
    return 0;
}

心路历程（其他超时代码）

我写的逻辑简单但超时代码

https://atcoder.jp/contests/abc375/submissions/58745887

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
string s;
long long ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(s[i]==s[j])
                ans+=j-i-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58745887

优化了一下，现在只TLE 4个点了

https://atcoder.jp/contests/abc375/submissions/58746864

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
map<char,vector<int> > a;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        a[s[i]].push_back(i);
    }
    for(map<char,vector<int> >::iterator it=a.begin();it!=a.end();it++) {
        vector<int> temp=it->second;
        for(int i=0;i<temp.size();i++) {
            for(int j=i+1;j<temp.size();j++)
                ans+=temp[j]-temp[i]-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58746864

AI的AC代码：

https://atcoder.jp/contests/abc375/submissions/58722299

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long count_palindromic_triples(const string &S) {
    int n = S.size();

    // 左侧和右侧字符频率计数
    unordered_map<char, long long> left_count, right_count;

    // 初始化所有字符都在右侧
    for (char c : S) {
        right_count[c]++;
    }

    long long result = 0;

    // 遍历每一个可能的中间字符
    for (int j = 0; j < n; ++j) {
        char middle_char = S[j];

        // 把当前的中间字符从右侧移到左侧
        right_count[middle_char]--;

        // 统计左右侧相同字符的三元组个数
        for (const auto& pair : left_count) {
            char char_in_left = pair.first;
            result += left_count[char_in_left] * right_count[char_in_left];
        }

        // 将当前中间字符添加到左侧计数
        left_count[middle_char]++;
    }

    return result;
}

int main() {
    string S;
    cin >> S;

    cout << count_palindromic_triples(S) << endl;

    return 0;
}

算法优化了，但WA了6个点

https://atcoder.jp/contests/abc375/submissions/58757772

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
int sum[30],cnt[30];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++) {
        int idx=s[i]-'A';
        ans+=i*cnt[idx]-sum[idx]-cnt[idx];
        sum[idx]+=i;
        cnt[idx]+=1;
    }
    cout<<ans<<endl;
    return 0;
}

我说怎么会没过，原来是没开long long

ABC-375-C -Spiral Rotation

Posted on 2024-10-12 Edited on 2026-04-06

题目大意

给定一个 $N \times N$ 的网格字符矩阵。对于每个 $i$ ( $1 le i le N/2$ )，将以 $(i, i)$ 为左上角、 $(N+1-i, N+1-i)$ 为右下角的正方形区域顺时针旋转 90 度。求最终的网格状态。

这题其实纯模拟是做不出来的，需要一些小的优化技巧（如上图）

更加具象化一点是这样

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
const int N=3010;
int n;
char g[N][N],ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            int d=min(min(n+1-i,i),min(n+1-j,j));   // 即从该点到最近边框的距离
            int x=i,y=j;
            for(int _=1;_<=(d%4);_++) {
                int xi=y,yj=n+1-x;
                x=xi,y=yj;
            }
            ans[x][y]=g[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}
// AC https://atcoder.jp/contests/abc375/submissions/58737053

纯模拟的TLE代码

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long ll;
const int N=3010;
int n;
char g[N][N],ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    }
    for(int i=1;i<=n/2;i++) {
        for(int x=i;x<=n+1-i;x++) {
            for(int y=i;y<=n+1-i;y++) {
                ans[y][n+1-x]=g[x][y];
            }
        }
        for(int x=i;x<=n+1-i;x++) {
            for(int y=i;y<=n+1-i;y++) {
                g[y][n+1-x]=ans[y][n+1-x];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            putchar(g[i][j]);
        }
        putchar('\n');
    }
    return 0;
}
// https://atcoder.jp/contests/abc375/submissions/58711404

牛客小白月赛102-D-最短？路径

Posted on 2024-10-11 Edited on 2026-04-06

题目大意

给定一个图，边有权值。在节点上每经过 k 条边必须休息一次（或者说每走 k 步必须停顿）。求从起点到终点的最短时间（或路径权值和），考虑休息带来的限制/代价。

AC代码

参考了官方题解思路，就是在分层图上跑最短路

相比于TLE代码，只加了个这个优化

while(!q.empty() && dist[n+1]==INF)

如果dist[n+1]已经确定，那就不用再跑了。

然后代码实现上有比较多的细节，主要是在初始化方面，比如说vis[i][0]也要清理什么的

// https://ac.nowcoder.com/acm/contest/91355/D
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N=2e5+10,INF=1e18+7;
ll T,n,m,k,a[N],u,v,dist[N];
vector<ll> e[N];
bool vis[N][11];
struct edge {
    ll node,dis,nrest; // nrest 为多久没休息了
};
struct cmp {
    bool operator()(edge a,edge b) {
        if(a.dis!=b.dis)
            return a.dis>b.dis;
        return a.node<b.node;
    }
};
priority_queue<edge,vector<edge>,cmp > q;
edge make_edge(ll node,ll dis,ll nrest) {
    edge temp;
    temp.node=node;temp.dis=dis;temp.nrest=nrest;
    return temp;
}
void dijkstra(int t) {
    q.push(make_edge(1,0,0));
    while(!q.empty() && dist[n+1]==INF) {
        ll node=q.top().node,dis=q.top().dis,nrest=q.top().nrest;
        q.pop();
        if(vis[node][nrest])    // 之前访问过，弹出
            continue;
        vis[node][nrest]=true;
        dist[node]=min(dis,dist[node]);
        for(int i=0;i<e[node].size();i++) {
            if(nrest>=k)
                q.push(make_edge(e[node][i],dis+a[node],0));
            else {
                q.push(make_edge(e[node][i],dis+a[node],0));
                q.push(make_edge(e[node][i],dis+1,nrest+1));
            }
        }
    }
}
void clear() {
    priority_queue<edge,vector<edge>,cmp > empty;
    swap(empty,q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;_++) {
        cin>>n>>m>>k;
        clear();
        for(int i=1;i<=n+1;i++)
            e[i].clear();
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        fill(&dist[1],&dist[n+2],INF);
        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=k;j++)
                vis[i][j]=false;
        for(int i=1;i<=m;i++) {
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        e[n].push_back(n+1);
        e[n+1].push_back(n);
        dijkstra(_);
        cout<<dist[n+1]<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128343

心路历程（WA，TLE，MLE……）

过了40% TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029

// https://ac.nowcoder.com/acm/contest/91355/D
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N=2e5+10,INF=1e18+7;
ll T,n,m,k,a[N],u,v,dist[N];
vector<ll> e[N];
bool vis[N][11];
struct edge {
    ll node,dis,nrest; // nrest 为多久没休息了
};
struct cmp {
    bool operator()(edge a,edge b) {
        if(a.dis!=b.dis)
            return a.dis>b.dis;
        return a.node<b.node;
    }
};
priority_queue<edge,vector<edge>,cmp > q;
edge make_edge(ll node,ll dis,ll nrest) {
    edge temp;
    temp.node=node;temp.dis=dis;temp.nrest=nrest;
    return temp;
}
void dijkstra(int t) {
    q.push(make_edge(1,0,0));
    while(!q.empty()) {
        ll node=q.top().node,dis=q.top().dis,nrest=q.top().nrest;
        q.pop();
        if(vis[node][nrest])    // 之前访问过，弹出
            continue;
        vis[node][nrest]=true;
        dist[node]=min(dis,dist[node]);
        for(int i=0;i<e[node].size();i++) {
            if(nrest>=k)
                q.push(make_edge(e[node][i],dis+a[node],0));
            else {
                q.push(make_edge(e[node][i],dis+a[node],0));
                q.push(make_edge(e[node][i],dis+1,nrest+1));
            }
        }
    }
}
void clear() {
    priority_queue<edge,vector<edge>,cmp > empty;
    swap(empty,q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;_++) {
        cin>>n>>m>>k;
        clear();
        for(int i=1;i<=n+1;i++)
            e[i].clear();
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        fill(&dist[1],&dist[n+2],INF);
        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=k;j++)
                vis[i][j]=false;
        for(int i=1;i<=m;i++) {
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        e[n].push_back(n+1);
        e[n+1].push_back(n);
        dijkstra(_);
        cout<<dist[n+1]<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=72128029

牛客小白月赛102-B-连分数

Posted on 2024-10-11 Edited on 2026-04-06

题目大意

求解无限连分数 x = a + 1/(a + 1/(a + …)) 的值。即求解方程 x = a + 1/x 的正根。

AC代码牛顿迭代法

x=a + \frac{1}{a + \frac{1}{a + \frac{1}{a + \cdots}}}

因为是无限的递归，可以把a下面的看成一个整体，其实也是x，然后你就把这个问题转化成了求一元二次方程。

x = a + \frac{1}{x}

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int T;
double a;

double solve(double a) {
    // 使用公式直接计算连分数的解
    return (a + sqrt(a * a + 4)) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    for(int _ = 1; _ <= T; _++) {
        cin >> a;
        double ans = solve(a);
        cout << setprecision(24) << ans << endl;
    }

    return 0;
}
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71962585

ABC-373-E - How to Win the Election

Posted on 2024-10-10 Edited on 2026-04-06

题目大意

有 N 个候选人争夺 M 个席位，共有 K 张票。目前已知每个候选人已获得的票数，以及剩余未投的票数。对于每个候选人，判断在最坏情况下（即剩余票数的分配对他最不利时），他是否还能通过获得一定数量的剩余票数来确保当选（进入前 M 名）。如果是，求出他至少需要再获得多少票；否则输出 -1。

AC代码

二分答案，检查器的设计重点在于
// 防止选用自己作为自己的竞争对手

1 2	if(idx-needOver-rectifyIdx<0) // <0 说明人不够了，一共就没那么多人（n=m） return true;

https://atcoder.jp/contests/abc373/submissions/58823933

二分检查器的核心行（加粗行）思路

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll diff=0;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi,rectify=0,rectifyIdx=0;
    // 防止选用自己作为自己的竞争对手
    ll candidateIdx=li[indexOfCandidate]-1;
    if(candidateIdx<=idx && candidateIdx>idx-needOver) {
        rectify=oa[indexOfCandidate],rectifyIdx=1;
    }
    // hand 11 过不了原因是n=m，我没有考虑人不够的情况 不知道他给你指到哪里去了
    if(idx-needOver-rectifyIdx<0)  // <0 说明人不够了，一共就没那么多人（n=m）
        return true;
    diff=gainBallots+(currBallots+1)*needOver-(sumA[idx]-sumA[idx-needOver-rectifyIdx]-rectify);
    // 就是下面循环的前缀和写法
    // for(ll i=idx;cnt<needOver;i--) {
    //     diff+=(currBallots+1-a[i]);
    //     cnt++;
    // }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=0,r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
        oa[i]=a[i];
    }
    remain=k-countedBallots;
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {     // 前缀和
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        ans[i]=bsearch(i);
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
// 只WA了一个点 https://atcoder.jp/contests/abc373/submissions/58815831
// AC https://www.luogu.com.cn/record/182236761
// AC https://atcoder.jp/contests/abc373/submissions/58823933

心路历程

我现在的想法就是我认为这就是博弈论，就是我投的票要竭力使这个人掉出m人的队列，而然后剩余的票一定是投在这个人身上
ans[i]=ceil((remain-diff)*1.0/(cnt+1));的来历

半成品代码

#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],toli[N]; // toli是通过a下标访问li的转介层
ll borderlineStand=0; // 临界标准，说人话就是不满足条件但最大的。
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
void debug() {
    cout<<"stand: "<<stand<<" borderlineStand:"<<borderlineStand<<endl;
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<li[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<toli[i]<<" ";
    }
    cout<<endl<<"ans: ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
        else
            borderlineStand=max(borderlineStand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
        for(ll j=s;j<e;j++) {
            toli[j]=i;       // toli 也可以认为是排序后元素位置->排序前元素位置
        }
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi+1-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }
    }
    debug();
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}

https://atcoder.jp/contests/abc373/submissions/58808859

五彩缤纷的提交

我做着做着发现完全不需要分两种情况，这个提交是分两种情况的。

然后check（）可以用前缀和优化

像这道题一样

#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi;
    ll cnt=0,diff=gainBallots;
    for(ll i=idx;cnt<needOver;i--) {
        diff+=(currBallots+1-a[i]);
        cnt++;
    }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=stand-oa[i],r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }else {         // 这里是原来没选上，如何在剩余选票中抢到位置
            ans[i]=bsearch(i);
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}