codeforces 724D(贪心)

题目链接:http://codeforces.com/contest/724/problem/D

题意:给定一个字符串和一个数字m,选取一个一个子序列s,使得对于字符串中任意长度为m的子序列都至少含有s的位置(不是字符),求所有s在sort后字典序最小的那个字符串。

思路:对字符排序后,从最后一个开始贪心,判断删除该字符后是否符和题意,当删除后不符合题意时,贪心到该相同字符对应的第一个位置为止。

比如对于test3来说

排序后为a a a b b b b c c c c

删除到(b,6)时发现不合题意了,该相同字符对应的第一个位置为(b,3),继续贪心到3为止,结果为a a a b(第二个b) b(第四个b)

 #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + ;
char a[N];
struct node
{
char c;
int id;
node() {}
node(char c,int i) : c(c), id(i) {}
bool operator < (const node &t)
{
if(c != t.c)
return c < t.c;
return id < t.id;
}
}q[N];
map<int,bool> mp;
map<int,bool>::iterator it;
int main()
{
int m;
scanf("%d",&m);
scanf("%s",a);
int len = strlen(a);
for(int i = ; i < len; i++)
{
q[i].c = a[i];
q[i].id = i;
mp[i]++;
}
mp[-] = ,mp[len] = ;
sort(q,q + len);
for(int i = len - ; i >= ; i--)
{
it = mp.find(q[i].id);
it--;
int t1 = (*it).first;
it++,it++;
int t2 = (*it).first;
if(t2 - t1 > m)
{
int t = lower_bound(q, q + i + , node(q[i].c,)) - q;
for(int j = ; j < t; j++)
printf("%c",q[j].c);
for(int j = i; j >= t; j--)
{
it = mp.find(q[j].id);
it--;
int t3 = (*it).first;
it++,it++;
int t4 = (*it).first;
if(t4 - t3 <= m)
{
it--;
mp.erase(it);
continue;
}
printf("%c",q[j].c);
}
return ;
}
it--;
mp.erase(it);
}
return ;
}
上一篇:Makefile,如何传递宏定义DEBUG【转】


下一篇:理解 Delphi 的类(十) - 深入方法[18] - 在接口区声明的方法都相当于提前声明了