Codeforces Round #638 (Div. 2) ABC

1819 단어 Codeforces
A - Phoenix and Balance
제목:
아이디어:
코드:
 
B - Phoenix and Beauty
제목: 길이가 n인 서열 a, 1<=a[i]<=n을 지정하면 임의의 위치에 [1,n]의 숫자를 삽입하여 모든 길이가 k인 자단을 일치하게 할 수 있습니다.할 수 있는지 묻고, 할 수 있다면 최종 시퀀스를 출력합니다.
아이디어:
코드:
 
C - Phoenix and Distribution
제목: n 길이의 문자열을 정하고 알파벳 하나하나를 k개의 작은 문자열로 나누십시오. 이 k개의 작은 문자열 중 사전 순서가 가장 큰 문자열의 가장 작은 문자열은 무엇입니까?
욕심 전략:
1. 문자열을 사전순으로 작은 순서에서 큰 순서로 정렬하기
2. 이동한 후 k자모에서 k자모로 나누어 k개의 빈열에 넣는다(현재 k자 문자열은 각각 1자모를 포함한다)
3. 원열이 한 자모만 남으면 최소 자모로 시작하는 문자열에 균등하게 펼친다
4. 그렇지 않으면 나머지 모든 자모를 최소 자모의 뒤에 넣는다
5. 답은 첫 번째 문자열과 k번째 문자열 중 비교적 큰 자
가장 큰 문자열을 최소화해야 하기 때문에,
만약 1가지 문자만 남았다면 e.g.k=3, ab, ab, b | abb, a, b, 나머지 문자'b'를 균등하게 나누어야 한다. abb가 ab보다 크고 최소 자모의 문자열까지 균등하게 나누어야 하기 때문이다. 그렇지 않으면 답이 커질 수 있기 때문이다.
만약 한 글자만 남은 것이 아니라면, 남은 모든 문자를 최소 자모 뒤에 e.g.k=2, abz, ab | abbz, a, 남은 가장 큰 문자 'z' 를 모두 넣어야 하기 때문에, 문자열의 위치를 가능한 한 뒤로 돌려야만 답안을 최소화할 수 있다
//그래, 내 논리가 좀 더 유창했으면 좋겠어.
코드:
#include
using namespace std;
typedef long long ll;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        string str;
        cin>>str;
        sort(str.begin(),str.end());

        //            cnt 
        auto pos=upper_bound(str.begin(),str.end(),str[0]);
        int cnt;
        if(pos==str.end()) cnt=k;
        else cnt=pos-str.begin();

        string s1,s2;
        s1+=str[0],s2+=str[k-1];//    
        
        if(str[k]!=str[n-1]) { //       1 
            s1+=str.substr(k);
        }else{ //      
            s1.insert(s1.end(),(n-k+cnt-1)/cnt,str[k]);
            //                            (n-k+cnt-1)/cnt  //(n-k)/cnt     +1
        }
        cout<

좋은 웹페이지 즐겨찾기