看到题解里有dalao离散化写得很妙,于是用这个思路写了一发:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct num
{
int wz;
bool flag;
ll w;
}a[50005];
bool cmp1(num x,num y){return x.w<y.w;/*if(x.w==y.w)return x.wz<y.wz;*/}
bool cmp2(num x,num y){return x.wz<y.wz;}
int t,n,l;
int main()
{
t=read();
while(t--)
{
n=read();
for(int i=1;i<=n;i++)
{
a[i].w=read();
a[i].wz=i;
a[i].flag=0;
}
sort(a+1,a+1+n,cmp1);
for(int i=1;i<=n;i+=l)
{
l=1;
for(int j=i+1;j<=n;j++)
{
if(a[i].w==a[j].w)a[j].flag=1,l++;
else break;
}
}
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++)
if(!a[i].flag)printf("%lld ",a[i].w);
printf("\n");
}
return 0;
}
然后全WA了,接下来我改了又改,几乎要和题解一模一样了:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct num
{
int wz,w;
}a[50005];
bool cmp1(num x,num y){return x.w>y.w;if(x.w==y.w)return x.wz<y.wz;}
bool cmp2(num x,num y){return x.wz<y.wz;}
int t,n,l;
int main()
{
t=read();
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a[i].w=read();
a[i].wz=i;
}
sort(a+1,a+1+n,cmp1);
for(int i=1;i<=n;i+=l)
{
l=1;
for(int j=i+1;j<=n;j++)
{
if(a[i].w==a[j].w)a[j].w=-2147483649,l++;
else break;
}
}
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++)
if(a[i].w!=-2147483649)printf("%lld ",a[i].w);
printf("\n");
}
return 0;
}
然而还是WA了,不明白啊……