魔鬼PAT训练 DAY3

4.4.贪心

B1023. 组个最小数(20')

#include <iostream>
using namespace std;
int main() {
    int num[10], i;
    for(i = 0; i < 10; i++)
        scanf("%d", num + i);
    for(i = 1; i < 10; i++)
        if(num[i]) break;
    printf("%d", i);
    num[i]--;
    for(i = 0; i < 10; i++)
        while(num[i]--) printf("%d", i);
    return 0;
}

B2020/A10700.月饼(25')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct mooncake {
    double cnt, price;
};
vector<mooncake> v;
bool cmp(mooncake mc, mooncake mc2) {
    return mc.price * mc2.cnt < mc2.price * mc.cnt;
}
int main() {
    double N, target;
    scanf("%lf %lf", &N, &target);
    v.resize(N);
    for(int i = 0; i < N; i++)
        scanf("%lf", &v[i].price);
    for(int i = 0; i < N; i++)
        scanf("%lf", &v[i].cnt);
    sort(v.begin(), v.end(), cmp);
    double ans = 0;
    for(int i = 0; i < N && target != 0; i++){
        if(v[i].price <= target){
            target -= v[i].price;
            ans += v[i].cnt;
        }else {
            ans += (target * v[i].cnt / v[i].price);
            target = 0;
        }
    }
    printf("%.2f", ans);
    return 0;
}

A1037.Magic Coupon(25')

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, M, a[999999], b[999999], ans = 0;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", a + i);
    scanf("%d", &M);
    for(int i = 0; i < M; i++) scanf("%d", b + i);
    sort(a, a + N); sort(b, b + M);
    for(int i = 0; i < min(N, M); i++)
        if(a[i] < 0 && b[i] < 0) ans += a[i] * b[i];
    for(int i = N - 1, j = M - 1; i >= 0 && j >= 0; i--, j--)
        if(a[i] > 0 && b[j] > 0) ans += a[i] * b[j];
    printf("%d", ans);
    return 0;
}

A1067.Sort with Swap(0, i) (25')

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> m;
int N, cnt = 0, tmp;
int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d", &tmp);
        m[tmp] = i;
    }
    for(int i = 1; i < N; i++) {
        if(i != m[i]) {
            while(m[0] != 0) {
                swap(m[0], m[m[0]]);
                cnt++;
            }
            if(i != m[i]) {
                swap(m[0], m[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

A1038.Recover the Smallest Number(30')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string s1, string s2) {
    return s1 + s2 < s2 + s1;
}
int main(){
    int N;
    cin >> N;
    vector<string> v(N);
    for(int i = 0; i < N; i++)
        cin >> v[i];
    sort(v.begin(), v.end(), cmp);
    string res;
    for(int i = 0; i < N; i++)
        res += v[i];
    while(res.length() != 0 && res[0] == '0')
        res.erase(res.begin());
    if(res.length() == 0) cout << 0;
    else cout << res;
    return 0;
}

4.5.二分

B1030/A1085.完美数列(25')

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    long long p;
    scanf("%d%lld", &n, &p);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int result = 0, temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + result; j < n; j++) {
            if (v[j] <= v[i] * p) {
                temp = j - i + 1;
                if (temp > result)
                    result = temp;
            } else {
                break;
            }
        }
    }
    cout << result;
    return 0;
}

A1048.Find Coins

#include <iostream>
#include <map>
using namespace std;
int main() {
    int N, M, tmp;
    map<int, int> m;
    scanf("%d%d", &N, &M);
    while(N--) {
        scanf("%d", &tmp);
        m[tmp]++;
    }
    for(auto it = m.begin(); it != m.end(); it++) {
        it->second--;
        if(m[M - it->first]) {
            printf("%d %d", it->first, M - it->first);
            return 0;
        }
    }
    printf("No Solution");
    return 0;
}

B1040/A1093. 有几个PAT

#include <iostream>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    long long P=0,A=0,T=0,sum=0;
    for(int i=0;i<s.length();i++)
        if(s[i]=='T') T++;
    for(int i=0;i<s.length();i++){
        if(s[i]=='P') P++;
        if(s[i]=='T') T--;
        if(s[i]=='A') sum+=((P%1000000007*T%1000000007)%1000000007);
    }
    cout<<sum%1000000007;
    return 0;
}

B1045/A1101.快速排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<int> res;
    int N, Max = -1;
    cin >> N;
    int arr[N], cp[N];
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
        cp[i] = arr[i];
    }
    sort(cp, cp+N);
    for(int i = 0; i < N; i++){
        if(cp[i] == arr[i] && arr[i] > Max)
            res.push_back(arr[i]);
        if(arr[i] > Max) Max = arr[i];
    }
    printf("%d\n",res.size());
    for(int i = 0; i < res.size(); i++)
        if(i != res.size() - 1) printf("%d ", res[i]);
        else printf("%d", res[i]);
    printf("\n");
    system("pause");
    return 0;
}

5.1.简单数学

B1003.我要通过

#include <iostream>
using namespace std;
string str; int N;
int main() {
    scanf("%d", &N);
    while(N--) {
        cin >> str;
        int P = 0, T = 0, no = false;
        while(str[P] != 'P' && P < str.length()) P++;
        while(str[T] != 'T' && T < str.length()) T++;
        if(P >= str.length() || T >= str.length() || T - P == 1) no = true;
        for(int i = 0; i < str.length(); i++)
            if(i != P && i != T && str[i] != 'A') no = true;
        if(P * (T - P - 1) != (str.length() - T - 1)) no = true;
        printf("%s\n", no ? "NO": "YES");
    }
    return 0;
}

A1069.数字黑洞

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N;
    scanf("%d", &N);
    string str, rev;
    do {
        str = to_string(N);
        while(str.length() != 4) str = "0" + str;
        sort(str.begin(), str.end());
        rev = str;
        reverse(rev.begin(), rev.end());
        N = stoi(rev) - stoi(str);
        printf("%s - %s = %04d\n", rev.c_str(), str.c_str(), N);
    }while(N != 0 && N != 6174);
    return 0;
}

A1008.Elevator(0')

#include <iostream>
#include <map>
using namespace std;
int main() {
    int N, level = 0, tmp, sum = 0;
    scanf("%d", &N);
    while(N--) {
        scanf("%d", &tmp);
        if(tmp > level) sum = sum + (tmp - level) * 6 + 5;
        else sum = sum + (level - tmp) * 4 + 5;
        level = tmp;
    }
    cout << sum;
    return 0;
}

B1019/A1104.数列片段和(20')

#include <iostream>
using namespace std;
int main(){
    int N; cin>>N;
    double a[N],sum=0;
    for(int i=0;i<N;i++) cin>>a[i];
    for(int i=0;i<N;i++)
        sum+=(a[i]*(i+1)*(N-i));
    printf("%.2f",sum);
    return 0;
}

A1049.Counting Ones(30')