操作系统：bank

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
#define M 100
#define N 200
int n, m;
int Resource[M];
int Max[N][M];
int Allocation[N][M];
int Need[N][M];
int Available[M];
int Work[M];
bool Finish[N];
int List[N]; //存放安全序列的下标序列
void initial() {
    //创建初始状态：先输入 Resource、Max 和 Allocation
    //再计算出 Need、Available。
    //填补程序
    puts("How many processes and how many resources are there");
    cin >> n >> m;
    cout << n << "\t" << m << "\n";

    puts("Resourse,Total amount of each resource(m)");
    For(i, 0, m - 1) cin >> Resource[i], Available[i] = Resource[i];
    For(i, 0, m - 1) cout << Resource[i] << "\t";
    pt;
    puts("The maximum demand of each resource for n processes");
    For(i, 0, n - 1) For(j, 0, m - 1) cin >> Max[i][j];
    For(i, 0, n - 1) {
        For(j, 0, m - 1) cout << Max[i][j] << "\t";
        pt;
    }

    puts("How many resources are currently allocated to each process");
    For(i, 0, n - 1) For(j, 0, m - 1) cin >> Allocation[i][j];
    For(i, 0, n - 1) {
        For(j, 0, m - 1) cout << Allocation[i][j] << "\t";
        pt;
    }

    // puts("How much does each process need for each resource to run now");
    For(i, 0, n - 1) For(j, 0, m - 1) Need[i][j] = Max[i][j] - Allocation[i][j];

    puts("Show the resources needed by each process currently");
    For(i, 0, n - 1) {
        For(j, 0, m - 1) { cout << Need[i][j] << "\t"; }
        cout << "\n";
    }

    For(i, 0, n - 1) For(j, 0, m - 1) Available[j] -= Allocation[i][j];
    puts("Current number of resources remaining");
    For(i, 0, m - 1) cout << Available[i] << "\t";
    pt;
}
void printState() {
    //输出当前的状态表|Process |Max |Allocation |Need |Available|
    //填补程序
    pt;
    pt;
    puts("Current state");
    cout << "|Process"
         << "|Max\t\t\t"
         << "|Allocation\t\t"
         << "|Need\t\t\t"
         << "|Available\t\t|";
    pt;
    For(i, 0, n - 1) {
        cout << "|P" << i << "\t|";

        For(j, 0, m - 1) cout << Max[i][j] << "\t";
        cout << "|";

        For(j, 0, m - 1) cout << Allocation[i][j] << "\t";
        cout << "|";

        For(j, 0, m - 1) cout << Need[i][j] << "\t";
        cout << "|";

        if (!i)
            For(j, 0, m - 1) cout << Available[j] << "\t";
        if (!i)
            cout << "|";
        else
            cout << "\t\t\t|";
        pt;
    }
    pt;
    pt;
}
// int isfinish() {
//返回同时满足两个条件;
//{1.Finish[i]=false 2.Need[i][j]≤Work[j]}
//的进程下标i(修改Finish[i]=true)，否则返回-1
//填补程序
//}
bool issafe() {
    //判定当前状态是否为安全状态
    //（返回 true 或 false），把安全序列的下标放入List[N]数组。
    //填补程序
    For(i, 0, n - 1) Work[i] = Available[i], Finish[i] = 0;
    int cnt = 0;
    For(i, 0, n - 1) {
        For(j, 0, n - 1) {
            int flag = 1;
            if (Finish[j])
                continue;
            For(k, 0, m - 1) if (Work[k] < Need[j][k]) flag = 0;
            if (flag) {
                Finish[j] = 1, List[cnt++] = j;
                For(k, 0, m - 1) Work[k] += Allocation[j][k];
                // cout << "j=" << j << " " << cnt << "\n";
            }
        }
        // cout << "i=" << i << "\n";
        if (cnt == n)
            return true;
    }

    return false;
}
void printList() {
    //输出安全序列表|Process |Work |Need |Allocation |Work+Alloc |Finish |
    //填补程序
    pt;
    pt;
    For(i, 0, m - 1) Work[i] = Available[i];
    puts("Current security sequence");
    cout << "|Process|Work\t\t\t|Need\t\t\t|Allocation\t\t|Work+"
            "Alloc\t\t|Finish\t|"
         << "\n";
    For(i, 0, n - 1) {
        cout << "|P" << List[i] << "\t|";

        For(j, 0, m - 1) cout << Work[j] << "\t";
        cout << "|";

        For(j, 0, m - 1) cout << Need[i][j] << "\t";
        cout << "|";

        For(j, 0, m - 1) cout << Allocation[List[i]][j] << "\t";
        cout << "|";

        For(j, 0, m - 1) {
            Work[j] += Allocation[List[i]][j];
            cout << Work[j] << "\t";
        }
        cout << "|";
        cout << "true\t"
             << "|";
        pt;
    }
    pt;
    pt;
}
void reqresource(int pos, int request[M]) {
    //表示第 i 个进程请求 M 类资源 request[M]
    // bool flag;
    // int j;
    // Step1: 判断条件 Request[j]≤Need[i][j]
    //填补程序
    // Step2: 判断条件 Request[j]≤Available[j]
    //填补程序
    // Step3: 预先分配
    //填补程序
    // Step4: 检测是否为安全状态
    //填补程序
    int flag = 1;
    For(i, 0, m - 1) {
        if (request[i] > Need[pos][i]) {
            puts("Request error:Request greater than the demand");
            cout << request[i] << " " << Need[i] << "\n";
            return;
        }
        if (request[i] > Available[i]) {
            puts("Request error:Request greater than available");
            cout << request[i] << " " << Available[i] << "\n";
            return;
        }
    }
    For(i, 0, m - 1) {
        Need[pos][i] -= request[i];
        Available[i] -= request[i];
        Allocation[pos][i] += request[i];
    }
    if (!issafe()) {
        puts("Resource request failed! Security check: enter unsafe state! ");
        puts("Restore previous state");
        For(i, 0, m - 1) {
            Need[pos][i] += request[i];
            Available[i] += request[i];
            Allocation[pos][i] -= request[i];
        }
    } else {
        puts("Successful resource application");
        puts("Show current security sequence");
        printList();
    }
}
int main() {
    // freopen("blank.in", "r", stdin);
    int reqid = -1, j, req[M];
    initial();
    printState();
    // cout << issafe() << endl;
    if (!issafe())
        puts("Initial state is unsafe!");
    // printf("Initial state is unsafe!\n");
    else {
        pt;
        puts("Initial state is safe!");
        // printf("\nInitial state is safe!\n");
        // For(i, 0, n - 1) cout << List[i] << " ";
        // pt;
        printList();
        puts("Input the id of request process: ( When input - 1 stops");
        while (cin >> reqid) {
            if (reqid == -1)
                break;
            if (reqid < 0 || reqid >= n)
                puts("Illegal input process ID");
            puts("Input request resources:");
            For(i, 0, m - 1) cin >> req[i];
            reqresource(reqid, req);
            printState();
            puts("Input the id of request process: ( When input - 1 stops");
        }
        // scanf("%d", &reqid);
        // while (reqid >= 0 && reqid < n) { //输入进程 id 是否合法
        //     printf("Input request resources:");
        //     for (j = 0; j < M; j++)
        //         scanf("%d", &req[j]);
        //     reqresource(reqid, req);
        //     printState();
        //     printf("Input the id of request process:");
        //     scanf("%d", &reqid);
        // }
    }
    return 0;
}

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
char s[N];
struct node {
    int key;        //进程ID
    int sequence;   //进程进入队列顺序号
    string massage; //进程说明信息
};
int main() {
    int count = 0;
    int n;
    puts("How many processes");
    cin >> n;
    // node *p,*q;
    puts("The new process control table:");
    puts("keysequence message");
    queue<node> que;
    For(i, 0, n - 1) {
        node tmp;
        cin >> tmp.key >> tmp.sequence >> tmp.massage;
        que.push(tmp);
    }
    puts("The table is:");
    queue<node> p;
    For(i, 0, n - 1) {
        node tmp = que.front();
        que.pop();
        cout << tmp.key << "\t" << tmp.sequence << "\t" << tmp.massage << "\n";
        p.push(tmp);
    }
    For(i, 0, n - 1) {
        pt;
        node tmp = p.front();
        p.pop();
        cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
             << ", sequence = " << tmp.sequence << ", message = " << tmp.massage
             << "\n";
    }
    return 0;
}
/*
4
22 1 process22
30 2 process30
13 3 process13
90 4 process90
*/

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
char s[N];
struct node {
    int key;        //进程ID
    int priority;   //进程进入队列顺序号
    string massage; //进程说明信息
    bool operator<(const node &a) const { return priority < a.priority; }
};
int main() {
    int count = 0;
    int n;
    puts("How many processes");
    cin >> n;
    // node *p,*q;
    puts("The new process control table:");
    puts("keysequence message");
    priority_queue<node> q;
    For(i, 0, n - 1) {
        node tmp;
        cin >> tmp.key >> tmp.priority >> tmp.massage;
        q.push(tmp);
    }
    puts("The table is:");
    priority_queue<node> p;
    For(i, 0, n - 1) {
        node tmp = q.top();
        q.pop();
        cout << tmp.key << "\t" << tmp.priority << "\t" << tmp.massage << "\n";
        p.push(tmp);
    }
    For(i, 0, n - 1) {
        pt;
        node tmp = p.top();
        p.pop();
        cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
             << ", sequence = " << tmp.priority << ", message = " << tmp.massage
             << "\n";
    }
    return 0;
}
/*
5
1 20 process1
2 50 process2
3 30 process3
4 10 process4
5 40 process5
*/

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;

struct node {
    int key;        //进程ID
    string massage; //进程说明信息
    int run_time;   //进程需要运行时间
};

queue<node> q;

void PrintCurrentState(int num) {
    if(num<=0) return;
    while(num--) {
        node tmp = q.front();
        q.pop();
        cout << tmp.key << "\t" << tmp.run_time << "\t" << tmp.massage << "\n";
        q.push(tmp);
    }
}


int main() {
    int count = 0;
    int n;
    int WaitTime = 0, cnt = 0;
    puts("How many processes");
    cin >> n;
    int num = 0;
    puts("The new process control table:");
    puts("keysequence message");
    For(i, 0, n - 1) {
        node tmp;
        cin >> tmp.key >> tmp.run_time >> tmp.massage ;
        q.push(tmp);
    }
    puts("The table is:");
    while(num--) {
        node tmp = q.front();
        q.pop();
        cout << tmp.key << "\t" << tmp.run_time << "\t" << tmp.massage << "\n";
        q.push(tmp);
    }
    while(q.size()) {
        pt;
        pt;
        node tmp = q.front();
        q.pop();
        cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
             << ", run_time = " << tmp.run_time << ", message = " << tmp.massage;
        pt;
        pt;
        if(tmp.run_time == 1) WaitTime++, tmp.run_time = 0;
        else WaitTime += 2, tmp.run_time -= 2;
        if(tmp.run_time) q.push(tmp);
        else n--;
        puts("Recent table is:");
        cout<<n<<"\n";
        PrintCurrentState(n);

//        int start_time = WaitTime;
//        cnt++;
//        WaitTime += tmp.run_time;
//        cout << "The " << ++count << "th scheduled process:\nkey = " << tmp.key
//             << ", sequence = " << tmp.sequence << ", message = " << tmp.massage
//             << ", AverageWaiting = " << (double) WaitTime / cnt << ", StartTime = "
//             << start_time << ", EndTime = " << WaitTime << ", RunTime = " << tmp.run_time 
//             
//             << "\n";
    }
}
/*
4
1 2 process1
2 4 process2
3 6 process3
4 3 process4
*/

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define pt putchar(10)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;

struct node
{
    int address;    //存储分区起始地址
    int length;     //存储分区长度
    int flag;       //存储分区标志，0 为空闲，1 为被作业占据
    string s;  //当 flag==1 时存储分区占用标志作业名，否则存储空 nil
    bool operator<(const node& x) const
    {
        return address > x.address;      //从小到大排序
    }
};
priority_queue<node> dtable1,ftable1,dtable2,ftable2;
void create1()
{
    puts("address length flag(0 or 1) end with 0 0 0");
    while(1)
    {
        int add,len,fl;
        cin>>add>>len>>fl;
        if(!add&&!len&&!fl) break;
        node tmp;
        tmp.address=add,tmp.flag=fl,tmp.length=len;
        printf("input job_name:");
        cin>>tmp.s;
        dtable1.push(tmp);
        pt;
        puts("address length flag(0 or 1) end with 0 0 0");
    }
}
void create2()
{
    puts("address length flag(0 or 1) end with 0 0 0");
    while(1)
    {
        int add,len,fl;
        cin>>add>>len>>fl;
        if(!add&&!len&&!fl) break;
        node tmp;
        tmp.address=add,tmp.flag=fl,tmp.length=len;
        tmp.s="nil";
        ftable1.push(tmp);
        pt;
        puts("address length flag(0 or 1) end with 0 0 0");
    }
    pt;
}
void show()
{
    pt;
    puts("The free table is :");
    while(ftable1.size())
    {
        node tmp=ftable1.top();
        ftable1.pop();
        cout<<tmp.address<<","<<tmp.length<<","<<tmp.flag<<","<<tmp.s<<endl;
        ftable2.push(tmp);
    }
    pt;
    puts("The distributed table is :");
    while(dtable1.size())
    {
        node tmp=dtable1.top();
        dtable1.pop();
        cout<<tmp.address<<","<<tmp.length<<","<<tmp.flag<<","<<tmp.s<<endl;
        dtable2.push(tmp);
    }
    pt;
}
bool chk(int len,string s)
{
    int jude=0;
    int flag=1;
    while(ftable2.size())
    {
        node tmp1=ftable2.top();
        ftable2.pop();
        if(flag&&tmp1.length>=len)
        {
            node tmp2;
            tmp2.length=len,tmp2.flag=1,tmp2.s=s;
            tmp2.address=tmp1.address;
            dtable1.push(tmp2);
            jude=1;
            flag=0;
            if(tmp1.length-len!=0)
            {
                tmp1.address+=len;
                tmp1.length-=len;
                ftable1.push(tmp1);
            }
        }
        else if(!flag||tmp1.length<len)
        {
            ftable1.push(tmp1);
        }
    }
    while(dtable2.size())
    {
        node tmp=dtable2.top();
        dtable2.pop();
        dtable1.push(tmp);
    }
    return jude;
}
int main()
{
    puts("The distributed table is:");
    create1();
    puts("The free table is:");
    create2();
    show();
    while(1)
    {
        puts("The length of worked job is:");
        int tmpl;
        cin>>tmpl;
        printf("The name of worked job is:");
        string tmps;
        cin>>tmps;
        if(chk(tmpl,tmps))
        {
            puts("distributing is successful");
            show();
        }
        else
        {
            puts("distributing is not successful");
            show();
        }
    }
}
/*
0 60 1
OS
60 40 1
Task1
132 50 1
Task2
626 174 1
Task6
438 92 1
Task5
205 15 1
Task4
160 40 1
Task3
0 0 0
100 32 0
150 10 0
200 5 0
530 96 0
220 218 0
0 0 0

*/