Time Limit: 1 second
Memory Limit: 128 MB

【問題描述】

　有一個整數序列，我們不知道她的長度是多少（即序列中整數的個數），但我們知道在某些區間中至少有多少個整數，用區間
[ai,bi,ci]來描述它，[ai，bi，ci]表示在該序列中處于[ai，bi]這個區間的整數至少有ci個。現在給出若干個這樣的區間，
請你求出滿足條件的最短序列長度是多少。如果不存在則輸出 -1。
【輸入格式】

第一行包括一個整數n(n<=1000)，表示區間個數；
　 以下n行每行描述這些區間，第i+1行三個整數ai，bi，ci，由空格隔開，其中0<=ai<=bi<=1000 而且 1<=ci<=bi-ai+1。

【輸出格式】

文件輸出只有一個整數表示滿足要求序列長度的最小值。

Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=t081

【題解】

先把n個ai,bi,ci按照ai第一關鍵字,bi第二關鍵字升序排;
然后逆序處理n個關系;
優先選ai..bi這個區間里面的前面部分(當然如果這個區間里面有些數字已經被選了就不用再選了),這樣優先選前面的部分,就能讓前面的關系更容易利用公共的部分;就是這樣的貪心吧.
轉換成編程語言就是升序枚舉啦^_^
(想不出來什么情況會無解..)

【完整代碼】

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1000+100;struct abc {int a,b,c;friend bool operator < (abc x,abc y){if (x.a==y.a){if (x.b==y.b)return true;elsereturn x.b<y.b;}elsereturn x.a < y.a;} };int n; bool bo[MAXN]; abc t[MAXN];int main() {//freopen("F:\\rush.txt","r",stdin);scanf("%d",&n);for (int i = 1;i <= n;i++)scanf("%d%d%d",&t[i].a,&t[i].b,&t[i].c);sort(t+1,t+1+n);for (int i = n;i >= 1;i--){for (int j = t[i].a;j <= t[i].b;j++)if (bo[j]){t[i].c--;if (t[i].c==0)break;}if (t[i].c!=0){for (int j = t[i].a;j <= t[i].b;j++)if (!bo[j]){t[i].c--;bo[j] = true;if (t[i].c==0)break;}}}int si = 0;for (int i = 0;i <= 1000;i++)if (bo[i])si++;printf("%d\n",si);return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7626662.html

總結

以上是生活随笔為你收集整理的【t081】序列长度(贪心做法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。