80分伪双指针求调
查看原帖
80分伪双指针求调
465029
Specter_LiZN楼主2024/11/6 11:36

rt,我怀疑是我的做法正确性有问题
排序,一个指针(i)从小到大看能不能被杀掉,另一个指针对应进行攻击的怪兽(tar=find_bigger(i))

#include <bits/stdc++.h>
#define f(i,a,b) for(int i=a;i<=b;i++)
#define Shion cout<<'\n'
const signed Miku =INT_MAX;
const signed N =1e5+5;
using namespace std;

int n,in[N],cnt;
// bool vis[N];
// priority_queue<int> que;

int find_bigger(int sta){
  if(in[n]==in[sta]){
    return -1;
  }
  f(i,sta+1,n){
    if(in[i]>in[sta]){
      return i;
    }
  }
  return -1;//should not return this
}
signed main(){
  freopen("duel.in","r",stdin);
  freopen("duel.out","w",stdout);
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n;
  f(i,1,n){
    cin>>in[i];
  }
  sort(in+1,in+n+1);
  if(in[n]==in[1]){
    cout<<n;
    return 0;
  }
  int tar=1;
  for(int i=1;i<=n&&tar<=n;i++){//i=>curr
    tar=find_bigger(i);
    // cout<<"tar"<<tar<<'\n';
    if(tar==-1){
      break;
    }
    else{
      while(in[i]<in[tar]&&tar<=n&&i<=n){
        i++,tar++,cnt++;//delete
      }
    }
  }
  cout<<n-cnt;
  return 0;
  Shion;
}
2024/11/6 11:36
加载中...