Codeforces Round #402 (Div. 2)
A. Pupils Redistribution
模拟大法好。两个数列分别含有n个数x(1<=x<=5) 。现在要求交换一些数使得两个数列含有某个数字的个数相同，求最少交换次数。
int v1[N],v2[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
int x;
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
for(int i=0; i<n; i++)
{
scanf("%d",&x);
v1[x]++;
}
for(int i=0; i<n; i++)
{
scanf("%d",&x);
v2[x]++;
}
int f=0;
int ans=0;
for(int i=1; i<=5; i++)
{
if(v1[i]==v2[i]) continue;
if(v1[i]>v2[i])
{
int num=v1[i]-v2[i];
for(int j=1; j<=5; j++)
if(j!=i&&v2[j]-v1[j]>=num)
{
v1[i]=v2[i];
v2[j]-=num/2;
v1[j]+=num/2;
ans+=num/2;
break;
}
}
else
{
int num=v2[i]-v1[i];
for(int j=1; j<=5; j++)
if(j!=i&&v1[j]-v2[j]>=num)
{
v1[i]=v2[i];
v2[j]+=num/2;
v1[j]-=num/2;
ans+=num/2;
break;
}
}
}
for(int i=1; i<=5; i++)
if(v1[i]!=v2[i]) f=1;
if(f) puts("-1");
else pd(ans);
}
return 0;
}
B. Weird Rounding
给你一个int范围内的数和一个k，求最少删除几个数字使得剩余的数字组成的数能被10^k整除，保证有解。
贪心：能被10^k整除说明后缀至少有k个0，只需从后往前遍历如果达到了k个0就不用删，如果还未达到k个0而出现了数字那么ans++,因为要删掉这个数字，如果没法再删除数字而k还未减为0，则输出len-1(只留一个0)
string s;
int v[50];
int main()
{
int k;
cin>>s>>k;
int len=s.size();
int num=0,ans=0;
for(int i=len-1;i>=0&&k;i--)
{
if(s[i]=='0') k--;
else ans++;
}
if(!k) cout<<ans<<endl;
else cout<<len-1<<endl;
C. Dishonest Sellers
贪心大法。小明要买n件商品，但每件商品在一周后都会打折，这并不意味会比原价要低。小明本周最少要买k件，现在给出这n件商品原价和打折后的价钱，求买n件商品最少花多少钱。
贪心思路：首先我们知道这k件商品肯定得按原价买，我们为了划算肯定买那些降价低的商品，然后其余的按最小价钱买即可。所以就是一个结构体排序：降价低的优先，买满k件（原价买）后按最小价钱买。
struct S
{
int a,b;
} p[N];
int cmp(S x,S y)
{
return x.a-x.b<y.a-y.b;
}
int v[N];
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
for(int i=0; i<n; i++)
scanf("%d",&p[i].a);
for(int i=0; i<n; i++)
scanf("%d",&p[i].b);
sort(p,p+n,cmp);
ll ans=0;
int x=n;
for(int i=0; i<n; i++)
{
if(k)
{
ans+=p[i].a;
k--;
}
else ns+=min(p[i].a,p[i].b);
} cout<<ans<<endl;
}
return 0;
}
D. String Game
做完C题后还有半小时的样子，这题然后就各种YY，最终没过本场掉11分结束。
题意：一个人在玩删字母游戏，给出原串和要删除的字母的位置的先后顺序，然后求最多能删多少个字母还能够得到串p。也就是说再继续删一个字母再也无法得到串p了。题目保证删除过程中能得到串p。
思路：二分答案O(n)判定
string s,p;
int a[N],v[N],len,len2;
int find(int k)
{
int l=0;
for(int i=0; i<len; i++)
if(v[i+1]>k)
{
if(s[i]==p[l]) l++;
if(l>=len2) return 1;
}
return 0;
}
int main()
{
memset(v,0,sizeof(v));
cin>>s>>p;
len=s.size();
len2=p.size();
int x;
for(int i=1; i<=len; i++) scanf("%d",&x),v[x]=i;
int l=0,r=len,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(find(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}